영호

문제 링크 https://www.acmicpc.net/problem/14501 나의 풀이 주의점 n + 1일에 퇴사를 하기 때문에 상담이 n+1 일에 끝나는 경우까지 고려해야 합니다. 처음 접근 1일부터 n일까지 해당 날짜의 상담을 진행하는 경우 안하는 경우를 고려해서 점화식을 세우려고 시도해봤습니다. 만약, 1일차 상담에 이틀이 필요할 때 3일차 상담을 진행하는 경우의 점화식을 어떻게 세울지 고민하다 결국 해결하지 못하고 구글링을 했습니다. 구글링 결과 1일 부터 시작하는 것이 마지막 n일부터 시작해서 dp테이블을 갱신합니다. n=7 7일차 상담은 이틀이 필요하기 때문에 7 + 2 > n+1 이므로, 상담을 진행할 수 없습니다. 2일차 상담의 경우 5일이 필요하기 때문에 max(20 + dp[5], d..

문제 링크 https://www.acmicpc.net/problem/1941 나의 풀이 잘못된 접근 잘못 세운 점화식 $$ dp[i] = dp[i - (가장 큰 제곱근 ^ 2)] + 1$$ 단순하게 가장 큰 제곱근의 제곱을 빼서 dp 테이블을 갱신하는 것이 최솟값이라고 생각을 했습니다. 예를 들어 i = 26의 경우 가장 큰 제곱근인 5의 제곱 25를 26에서 뺀 뒤 나온 1. 즉, dp[26-25] + 1 이 무조건 최솟값이라고 생각했습니다. $$ 26 = 1^2 + 5^2$$ 올바른 접근 점화식의 경우 위에서 세운 점화식이 아예 틀린 것은 아니지만 가장 큰 제곱근만 생각하는 것이 아닌 1 ~ 가장 큰 제곱근의 경우를 모두 생각해야 합니다. 12를 시도해보면 좋을 거 같습니다. $$ dp[i] = m..

문제 링크 https://www.acmicpc.net/problem/9465 나의 풀이 우선, 3xn 크기의 dp테이블과 2xn 크기의 stickers배열을 생성합니다. dp[0][n] stickers[0][n]의 스티커를 뜯었을 때의 최댓값을 저장하고, 두 번째 행도 이와 마찬가지입니다. dp[2][n]은 stickers[0][n], stickers[1][n] 모두 뜯지 않았을 때의 최댓값을 저장합니다. 스티커를 뜯는 방식으로 3가지를 고려할 수 있습니다. 0행의 n열 스티커를 뜯는 경우 -> stickers[0][n]을 뜯는 경우 stickers[0][n]을 뜯은 경우 이와 인접한 stickers[0][n-1] 스티커는 뜯을 수 없기 때문에, stickers[0][n-1] 스티커를 뜯지 않은 경우인..