MathTrauma

문제 링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 색 r,g,b 를 0,1,2 에 대응시키자. 주어진 입력은 $ arr[i][k] ( 1 \le i \le n \; , \; 0 \le k

문제 링크 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동전의 종류 N 이고 만들어야 할 금액은 V 이다. $recur(n,v)$ 는 $n \; (1\le n \le N)$ 번 이하의 동전들을 사용해서 v 금액을 만드는 방법의 수이다. #include using namespace std; int N,V; int arr[21]; int dp[21][10001]; int recur(int n, int v){ if(n==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/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 결합 순서에 따라 비용이 달라지는 유명(?)한 문제이다. 위의 예를 들여다 보면 dp[a][b] = min(dp[a][b], dp[a][i] + dp[i+1][b] + (a 행렬의 행) * (i 행렬의 열= i+1 행렬의 행) * (b 행렬의 열) ); 을 얻을 수 있다. 전체 코드는 아래와 같다. #include using namespace std; vector arr..

문제 링크 : 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]..