MathTrauma

문제 링크 : https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 1. dp 의 정의 좌표 ( i , j ) 에 진입하는 방식에 따라 다음 움직임이 제한된다. 즉, 진입 방향을 기록할 필요가 있다. dir 은 진입 방향을 나타내는데 사용한다. (1, 1) 이 좌측 상단을 위미한다고 할 때, dir=1 은 위에서 아래로, dir=0 은 오른쪽에서, dir=2는 왼쪽에서 진입을 나타낸다. dp[i][j][dir]은 ( 1, 1 ) 에서 이동하..

문제 링크 : https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 1. dp 의 정의 dp[t][p][r] : t 시간에, p 번 나무 아래에서 움직일 수 있는 횟수가 r 번 남아 있을 때의 최댓값. 단, p 는 0, 1 값을 가지고 이는 1 , 2 번 나무를 뜻한다. 주인공 자두는 1 번 나무 아래에서 시작한다는 조건이 있는데 0 초에 0(1 번나무)에서 시작하는 것으로 설계하면 된다. 2. Transition 나무 위치 p 와 t 번째 입력(시간 t 에..

문제 링크 : https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net $ dp[n][k] $ 는 n 을 만드는 과정에서 마지막 수가 k( =1,2,3)인 경우의 수를 뜻한다. 1. Bottom-Up 예를 들어 보자. dp[10][2] 는 2로 끝나면서 10 을 만드는 경우의 수이다. 2 를 연이어 쓸 수 없으니 덧붙일 수 있는 것은 1, 3. 1 을 덧붙여 dp[11][1] 을 만드는데 기여하고, 3을 덧붙여서 dp[13][3] 을 만드는데 기여한다. $ dp[i][j] $ 를 i 를 1 부터 차례로 ..

문제 링크 : https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 탑다운, 바텀업 모두를 빠르게 작성하는 연습. 자연수 i 를 제곱수들의 합으로 표현할 때 필요한 제곱수의 개수를 최소화하라는 문제이니, 이를 dp[i] 라 두자. i 이하의 수에 대해서 최소화된 개수를 모두 알고 있다면 다음이 성립한다. $$ dp[i]= \min\limits_{j^2 \le i} dp[i-j^2] +1$$ 1. Bottom-UP ..

문제 링크 : https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 조건에서 메모리의 크기가 비용의 크기보다 훨씬 범위도 넓고 큰 값을 다룬다. 문제를 다르게 해석하는 것이 풀이를 용이하게 만들어 줄 듯하다. 일정량의 메모리를 확보하기 위한 최소 비용을 구하기 보다 일정 비용으로 확보할 수 있는 최대 메모리를 구해보자. 즉, dp[i][j] 를 i 번째 앱까지 j 비용으로 확보할 수 있는 최대 메모리로 두겠다는 의미이다. #include using name..

문제 링크 : https://www.acmicpc.net/problem/2011 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 입력을 문자열 str 로 받아서 처리한다. p 를 문자열에서 현재 처리할 index 라 하자. dp[p] 는 p 를 시작 위치로 하는 부분 문제의 결과값을 의미한다. 세 가지 가능성이 있다. 1. 더 이상 진행이 불가능한 경우 -> str[p] 가 '0' 이 경우 해당 수를 알파벳에 대응시킬 방법이 없다. 더 이상 진행하지 않고 return 0 을 하면 된다. 가짓수를 세는 문제니 0 을 돌려준다는 ..

문제 링크 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 주어진 연산을 이용해서 n 을 1 로 만드는데 필요한 비용(횟수) 외에도 경로도 출력한다는 것을 빼면 평범한 dp 문제. n 을 무엇으로 줄이면 최적인가를 기록해두는 prv 배열을 도입하면 충분하다. 탑다운 방식과 바텀업 방식을 모두 소개하기 쉬운 문제라 기록해 둔다. 1. Top-Down dp[n] 은 에 dp[n/3]+1 , dp[n/2]+1 이거나 dp[n-1]+1 중 작은 값이다. ( n 이 2, 3 의 배수가 아니면 앞의 항들은 사용하지 않는다.) #include using na..

문제 링크 : https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프가 점거하는 두 점 중에서 목적지에 가까운 점(행 또는 열의 좌표가 큰점)을 기준으로 dp 를 구성한다. dp[i][j][0] 은 가로, dp[i][j][1] 은 세로 그리고 dp[i][j][2] 는 대각선으로 놓인 상태이다. 전이는 0 이 되려면, 즉 가로로 놓을 수 있으려면 원래 0 (가로), 2(대각선) 상태에서 가능하다. \[ dp[i][j+1]..