백준 27219번: 신을 모시는 사당 (Java 코드)

풀이 solved.ac 기준 골드 5 난이도의 문제이다. dp 알고리즘을 이용해 문제를 해결할 수 있다. dp[] 배열을 만들고 i번째 돌상을 색칠할 경우에 얻을 수 있는 최대의 깨달음 양을 dp[i]에 저장해야 한다. 이 때 돌상이 바라보는 방향은 1(왼쪽)과 2(오른쪽) 두 가지 종류가 있으므로 dp배열도 두 개를 생성한다.(왼쪽으로 바라보는 불상으로 깨달음을 얻을 수도, 오른쪽으로 바라보는 불상으로 깨달음을 얻을 수도 있으므로!) dp 관련 코드는 다음과 같다. if (dir[i] == 1) { dp1[i] = (dp1[i-1] + 1 > 1) ? dp1[i-1] + 1 : 1; dp2[i] = dp2[i-1] - 1; } else { dp1[i] = dp1[i-1] - 1; dp2[i] = (dp..
카테고리 없음 2023. 1. 16. 12:59
1