221029 문제 풀이 기록

P3 | 10759 - 팰린드롬 경로 3

풀이 시간: 1시간 10분 + a

시도 횟수: X

체감 난이도: P3

풀이 쓸 의향: 下

풀이

중앙에 있는 부분부터 시작해서, 현명하게 DP값 찾기. 특정 위치 (y, x)까지 도달했을 때의 경로의 갯수를 저장해 주면 됨.

여담: 맞왜틀 후 답지보고 풀었음 : 풀이는 맞았었는데 구현에서 고꾸라져서 틀린 것으로 보임 :(

 

 

 

P3 | 18264 - Moortal Cowmbat

풀이 시간: 42분

시도 횟수: 3회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

일단 플로이드-워셜로 모든 M*M개의 경우에 대해 치환하는 최솟값을 구해두고 나서, DP[i][j] = i번째 index까지를 문자 j로 바꿨을 때의 최솟값 으로 두자. 부분 합을 토대로 [x, y] 구간의 모든 문자열을 j로 바꾸는 비용은 O(1) 안에 구할 수 있다.

dp[i][j] = min(sum[i][j], dp[i-1][j] + sum[i][j] - sum[i-1][j])로 초기화해둔 다음에,

dp[i][j] = min(dp[i][j], dp[i-K][x] + sum[i][j] - sum[i-K][j]) for all 0 < x < M;

으로 두면 O(NM^2)으로 해결 가능.

여담: 문제 제목 보고 혼자 쪼갰음. 어떻게 문제 이름을 저렇게 짓지 ㅋㅋㅋ

처음에 n m 헷갈려서 -1, dp 배열 초기화 제대로 안해줘서 -1;

그보다 요즘 DP 문제들을 엄청 많이 풀고있는 느낌이다. 흠,,