hyeonae

문제 풀이 Java로 풀려다가 시간 초과가 떠서 c++ 코드로 바꿔 해결했다. (테스트가 끝나고 서치해보니 Java에서 Scanner 대신 BufferedReader로 입력을 받아 시간을 줄이는 방법이 있는 것 같았다.) 복잡한 그림이 같이 있어서 당황했는데 문제는 생각보다 간단하다. 입력받은 맵에서 0으로 표시된 구역의 개수를 리턴하면 된다. 단, 조건은 처음과 끝이 연결되어 있는 도넛 행성이라는 점이다. 첫번째 행은 마지막 행과, 첫번째 열은 마지막 열과 연결되어 있으므로 이 부분을 조심해야 한다. 0으로 표시된 구역의 개수를 구하는 유형의 문제는 무조건 dfs를 이용해 해결한다. arr 배열에는 0과 1의 정보를 저장한다. visited 배열에는 해당 좌표의 방문 여부를 저장한다. int arr[M..

풀이 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..