다이나믹 프로그래밍5 [BOJ] 백준 1149번: RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 동적 계획법을 사용하는 문제입니다. i번째 집을 j번째 색으로 칠할 때의 비용 color[i][j]에 대하여 i번째 집까지 색을 칠할때 i번째 집을 j번째 색으로 칠하는 최소비용을 dp[i][j]라고 한다면 이웃한 집은 같은색으로 칠하면 안되므로 dp[i][j] = min(dp[i][j], dp[i-1][k] + color[i][j]) 단, k ≠ j 이 됩니다. #include #incl.. 2020. 10. 21. [BOJ] 백준 1014번: 컨닝 https://www.acmicpc.net/problem/1014 1014번: 컨닝 문제 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼 www.acmicpc.net 교실 정보가 주어질 때, 위의 그림처럼 컨닝이 가능해 A,C,D,E 중 한 자리라도 사람이 앉아있으면 컨닝을 방지하기 위하여 해당 자리를 앉지못하게 합니다. 위의 규칙을 만족하면서 최대한 몇명의 사람이 앉을 수 있는지 구하는 문제입니다. 저는 동적계획법으로 해결하였습니다. (입력이 10X10이므로 꽤 다양한 알고리즘으로 해결가능하다고 생각합니다.) DP[i][j] 는 i-1번째 줄에 j 상태로 앉아있을 때 i번째.. 2020. 8. 11. [BOJ] 백준 10217번: KCM Travel https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세�� www.acmicpc.net M원 이하로 1번 도시에서 N번 도시까지 갈 수 있는 경로 중 최단시간을 요구하는 문제입니다. 두가지 방법이 있는데 저는 동적계획법으로 해결했습니다. DP[i][j] 배열을 i 도시에서 j원으로 출발할 때 n 도시까지 걸리는 최단 시간으로 정의했습니다. 주의할 점은 입력 중 출발공항과 도착공항이 같은 여러개의 티켓 정보가 들어올 수 있다는 점입니다. (이걸.. 2020. 8. 9. [BOJ] 백준 1509번: 팰린드롬 분할 Class 5에는 대부분 DP로 구성된 것 같네요 recv(i)를 i번째 문자부터 시작했을때 가능한 최소 팰린드롬 수 DP[i]를 찾는 함수로 정하면 i = e) { return pal[s][e] = 1; } int& ret = pal[s][e]; if (~ret) return ret; ret = 0; if (str[s] == str[e]) { return ret = ispal(s + 1, e - 1); } return ret; } int recv(int node) { if (node == n) { return 0; } int& ret = dp[node]; if (~ret) return ret; ret = 2e9; for (int i = node; i < n; i++) { if (ispal(node, i.. 2020. 6. 25. 이전 1 2 다음
