https://www.acmicpc.net/problem/1520 풀이굉장히 어려웠던 문제입니다. DFS와 메모이제이션 기법을 적절히 사용해야 하는 문제였습니다. 풀이를 생각하지 못 하고 검색을 통해 해결했습니다. 첫 번째는 완전 탐색을 떠올렸습니다. DFS와 백트래킹 기법을 사용해서 완전 탐색을 하면 갈 수 있는 길의 개수를 구할 수 있습니다. 하지만 N과 M의 최대 크기는 500이었고 최대 칸의 개수는 250,000이었기 때문에 시간 초과가 발생합니다. 두 번째는 DP를 떠올렸습니다. dp[x][y]를 "좌표 (x, y)까지 도착할 수 있는 경우의 수"라고 정의하면 문제를 해결할 수 있을 것 같았습니다. 그래서 (0, 0)부터 (n-1, m-1)까지 dp 값을 구하면 해결할 수 있을 것 같았는데 문제..

가장 끝 날짜부터 첫 날짜로 오면서 dp를 수행했다. dp[i]의 의미는 끝 날짜부터 i 날짜까지 얻을 수 있는 최대 이익이다. dp[i]의 값은 다음 두 가지 경우를 고려해야 한다. i번째 날짜에 해당하는 상담을 진행한다.i번째 날짜에 해당하는 상담을 진행하지 않는다.두 경우 중 큰 값을 골라야 한다. 1번을 생각해보자. 해당 날짜에 상담을 진행할 경우 그 상담으로 받을 수 있는 금액과 그 상담이 끝난 날짜 이후부터 얻을 수 있는 최대 이익을 더하면 최대 이익이 된다. 2번을 생각해보자. 해당 날짜에 상담을 진행하지 않을 경우 그 날짜 이후부터 상담으로 얻을 수 있는 최대 이익이 해당 날짜의 최대 이익이 된다. 두 경우 중 더 큰 값이 최대 이익이 된다. 여기서 중요한 점은 특정 날짜 이후부터 상담으로..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net dp[x][y]를 다음과 같이 정의한다. dp[x][y]는 첫 번째로 입력받은 문자열을 s1이라 하고 두 번째로 입력받은 문자열을 s2라고 한다면 s1에서 x번째 문자까지와 s2에서 y번째 문자까지를 비교했을 때 최장 공통 부분 수열의 길이이다. 예를 들어 dp[2][4]라고 한다면 "AC"와 "CAPC"의 최장 공통 부분 수열의 길이인 "AC"즉, 2..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net dp를 활용하여 삼중 반복문을 사용하여 푸는 문제이다. dp[x][y]는 다음과 같이 정의한다. 인덱스 x 파일부터 인덱스 y 파일까지 하나의 파일로 합치는데 필요한 최소비용 이를 이용하여 dp 알고리즘을 적용하면 된다. 가장 먼저 x와 y가 동일한 경우를 보자. 다음과 같이 파일들의 크기를 나열할 때 15 1 21 3 4 5 35 5 4 3 5 98 21 14 17 32 dp[0][0]..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net dp로 문제를 풀어보았다. dp[i]의 값은 N이 i일 때의 배달하는 봉지의 최소 개수이다. 만들 수 없다면 -1을 저장한다. 1. 먼저 길이가 N+1이고 모든 값이 -1인 리스트를 생성한다. dp=[-1]*(n+1) 만약 N킬로그램을 만들 수 없는 경우 dp[i]의 값을 변경하지 않으면 된다. 2. dp[1]부터 dp[5]까지는 미리 값을 넣어준다. dp[1:6]=[-1, -1, 1, -1, 1]​ 3. ..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 일단 dp[i]의 값을 i를 제곱수들의 합으로 표현할 때 최소 개수로 정한다. 그렇게 되면 dp[i]의 값은 dp[1] + dp[i-1] dp[2] + dp[i-2] dp[3] + dp[i-3] . . . 위 값들 중 가장 작은 값이 된다. 처음엔 위 방식으로 이중 반복문을 돌려서 답을 구했으나 시간 초과가 발생했다. 시간을 더 줄일 수 있는 알고리즘을 사용..