mojo's Blog

문제 링크 : 12013번: 248 게임 (acmicpc.net) 12013번: 248 게임 이 예에서, Bessie는 두 번째와 세 번째에 있는 1을 2로 합친다. (1 2 2) 두 번째와 세 번째에 있는 2를 3으로 합친다. (1 3) 첫 번째와 두 번째 1을 합치는 것은 최적해가 아님을 주의해라. www.acmicpc.net Bessie 는 두 개의 인접한 수가 같을 때 (인접한 수 + 1) 로 합칠 수 있다고 한다. 즉 이러한 작업을 계속 하여 더이상 진행이 되지 않도록 하는 수열에 대해서 가장 큰 수를 구하는 문제이다. 위 문제를 다이나믹 프로그래밍으로 \(O(N^{3})\) 시간복잡도로 해결했다. ※ 접근 방법 1. dp[l][r] 을 [l, r] 범위 내에 얻을 수 있는 최대 점수라고 설정하..

문제 링크 : 1949번: 우수 마을 (acmicpc.net) 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 트리에서의 다이나믹 프로그래밍 문제이다. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마..

문제 링크 => 2342번: Dance Dance Revolution (acmicpc.net) 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다. DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의..

문제 링크 : 1509번: 팰린드롬 분할 (acmicpc.net) 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 1. PAL[x][y] : [x, y] 에 속한 부분 문자열이 팰린드롬이면 true, 아니면 false 를 나타내도록 한다. 이 부분은 다이나믹 프로그래밍을 통해 쉽게 구할 수 있다. 2. dp[x] : 인덱스 x 지점 까지의 최소 분할 갯수를 나타내도록 한다. dp[0] = 1 으로 채운 후 1 부..

문제 링크 => 10251번: 운전 면허 시험 (acmicpc.net) 10251번: 운전 면허 시험 만일 G 이하의 연료량으로 s에서 t까지 가는 것이 가능하다면 가능한 한 빨리 도착했을 때 걸리는 시간을, 불가능하다면 -1을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 아무래도 여러번 recursion을 이용한 memoziation 기법을 이용해서 해결하려고 했으나 시간초과가 계속 뜬다. 그래서 4차원 배열을 설정하여 다음과 같이 해결하였다. dp(curX, curY, turn, direction) = (curX, curY) 에서 turn 번 회전하여 direction 방향을 바라볼 때의 최소 연료량 먼저 시작지점에서부터 오른쪽 방향, 아래쪽 방향으로 가는 것은 회전하는 것이..

문제 링크 => 1937번: 욕심쟁이 판다 (acmicpc.net) 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 어떠한 지점 (x, y) 에서 존재하는 대나무를 먹고 다음 지점(nextX, nextY) 으로 이동할 때, 다음 지점(nextX, nextY) 에 존재하는 대나무의 갯수가 (x, y) 지점에 있던 대나무의 갯수보다 클 경우 다음 지점으로 이동하여 대나무를 먹는다. 이렇게 판다가 이동하면서 대나무를 야무지게 먹을 수 있는 최대 거리를 구해야 한다. 알 수 ..