목록백준 1028 C++ (1)

1일1알

백준 1028번 다이아몬드 광산 C++

dp[행][열][방향] 3차원 dp배열을 만든다. 방향은 0, 1, 2, 3 순서로 왼쪽 위, 오른쪽 위, 오른쪽 아래, 왼쪽 아래이다. dp[행][열][방향] 에 들어가는 수는 (행, 열) 에서 [방향] 쪽으로 이어지는 1의 개수이다. 배열을 위에서 아래로 순회하면서 왼쪽 위, 오른쪽 위 즉 dp[행][열][0], dp[행][열][1] 을 그 전 좌표의 값 + 1로 채워주고 아래에서 위로 순회하면서 오른쪽 아래, 왼쪽 아래 즉 dp[행][열][2], dp[행][열][3] 을 그 전 좌표의 값 + 1로 채워주었다. 다시 배열을 순회하면서 아래로 뻗어지는 두 수 중 작은 값을 기준으로 밑으로 내려가서 밑에서 위로 올라가는 수 중 작은 값이 앞에서 구한 값보다 크거나 같으면 다이아몬드를 만들 수 있다. 이 ..
알고리즘 2022. 2. 17. 15:50
이전 Prev 1 Next 다음