백준 10109, Troyangles

개요

문제 링크
골드4, DP
모든 삼각형 모양의 개수 구하기

---

접근

1. 골드 DP문제 부터 차근차근 연습해보자. 이게 문제가 현재 위치와 왼, 위, 오른쪽의 개수를 비교하는 문제인 건 바로 알겠는데, 문제는 오른쪽이 업데이트 되기 전에 현재 위치를 오른쪽과 비교해버리니 오류가 난다.
2. 그러자고 O(N^3)을 돌리자니 시간초과가 난다. 이럴때는 왼쪽 덩이와 오른쪽 덩이를 따로 만들어 둘의 최솟값을 구해주면 된다.
3. 왼쪽 덩이는? 왼쪽과 위쪽을 비교하고, 오른쪽 덩이는 오른쪽과 위쪽을 비교한다. 나머지는 -1인덱스 방지하기 위해 입력을 잘 해주면 크게 어렵지 않다.

---

Pseudo code

for (i=세로)
    for (j=가로)
        // 왼쪽 덩이 크기
        Left = min(Left[왼],Left[위])+1
    for (j=가로,오른쪽부터)
        // 오른쪽 덩이 크기
        Right = min(Right[오],Right[위])+1
    for (j=가로)
        dp[i][j]=min(Left,Right)

---

Source code

#include <iostream>
using namespace std;

#define N 2010

char a[N][N];
int L[N][N],R[N][N];
int main() {
    int n;
    cin>>n;
    int ans=0;
    for (int i=1;i<=n;i++) {
        scanf("%s",&a[i][1]);
        for (int j=1;j<=n;j++) {
            if (a[i][j]!='#') continue;
            L[i][j]=min(L[i-1][j],L[i][j-1])+1;
        }
        for (int j=n;j;j--) {
            if (a[i][j]!='#') continue;
            R[i][j]=min(R[i-1][j],R[i][j+1])+1;
            ans+=min(L[i][j],R[i][j]);
        }
    }
    cout<<ans;
}