[C++] 백준 2156번 포도주 시식
다이나믹 프로그래밍 문제입니다. 연속으로 3개의 포도주를 마시지 않으면서 최대한 많이 포도주를 마셨을때의 값을 찾는 문제입니다. 1. 현재 포도주를 안 먹었을 때 2. 현재 포도주를 먹지 않았고 이전 포도주를 먹었을 때 3. 현재 포도주와 이전 포도주 둘 다 먹었을 때 이렇게 3가지로 나타낼 수 있습니다. 코드로 작성하면 memo[i] = memo[i-1]; memo[i] = memo[i-2] + drink[i]; memo[i] = memo[i-3] + drink[i-1] + drink[i-2]; #include #include using namespace std; int memo[10010]; int drink[10010]; void init() { for (int i = 0; i < 10010; ++..
[C++] 백준 1003번 피보나치 함수
다이나믹 프로그래밍 문제입니다. 위의 피보나치 함수를 실행할때 fibonacci(0)과 fibonacci(1)이 각각 몇번 실행되는지 구하는 문제입니다. 0이면 0을 리턴해주므로 0 = (1 0) 1이면 1을 리턴해주므로 1 = (0 1) 2면 2-1, 2-2를 실행시키므로 2 = (1 0) + (0 1) 2 = (1 1)이 됩니다. 3도 마찬가지로 3-1, 3-2를 실행시키는 방식으로 구할 수 있습니다. memo[50][2]를 선언하였고 앞배열은 숫자 뒤에 배열은 0과 1의 개수를 넣었습니다. memo[i][0] = memo[i-1][0] + memo[i-2][0]; // 0의 개수를 구함 memo[i][1] = memo[i-1][1] + memo[i-2][1]; // 1의 개수를 구함 위의 코드를 찾..
[C++] 백준 1932번 정수 삼각형
다이나믹 프로그래밍 문제입니다. 피라미드모양에 각각 값들이 들어가있습니다. 위에서부터 왼쪽이나 오른쪽을 통해 내려올 때 합이 최대가 되는 경로의 값을 찾는 문제입니다. 경우의 수는 1. 위치가 가장자리일 때 2. 위치가 중앙일 때 2가지가 있습니다. 1번의 경우 바로 위의 값을 더해서 DP에 넣어주고 2번의 경우 바로 위의 값이 더할 수 있는 두개의 수를 비교해서 큰값을 더해서 DP에 저장합니다. #include #include using namespace std; int main(int argc, char *argv[]) { int n; int value = 0; int arr[510][510]; cin >> n; for(int i=0; i arr[i][j]; } } for(int i=1; i
[C++] 백준 2193번 이친수
다이나믹 프로그래밍 문제입니다. 문제의 규칙으로는 1. 0과 1로만 이루어져 있습니다.. 2. 0으로 시작하지 않습니다. 3. 1이 두번 연속 나타나지 않습니다. 와 같은 규칙을 가지고 있습니다. 이때 N자리 이친수의 개수를 출력하는 문제입니다. 1부터 차례대로 결과값을 생각해보면 1 - 1 2 - 10 3 - 100, 101 4 - 1000, 1001, 1010 5 - 10000, 10001, 10010, 10100, 10101 ... 와 같이 값이 나옵니다. 여기서 규칙을 찾을 수 있습니다. 1 = 1개 2 = 1개 3 = 2개 4 = 3개 5 = 5개 6 = 8개 7 = 13개 n = n-1 + n-2의 모양인 피보나치 수열의 모습을 가지고 있는것을 확인할 수 있습니다. arr[i] = arr[i-..
[C++] 백준 1149번 RGB거리
다이나믹 프로그래밍 문제입니다. 파란색, 빨간색, 초록색이 존재하고 이웃하는 집에는 같은색을 칠할 수 없습니다. 각각 집마다 페인트의 가격이 다르므로 최소의 돈을 써서 페인트를 칠하는 문제입니다. memo[1000][3] 배열에 각각의 집마다의 페인트 가격을 입력합니다. 현재 위치에서의 색과 전의 이웃에서의 색이 같으면 찾을 필요없기에 다른 색인 곳만 찾아서 적은 값인 곳을 현재 값과 더해주면서 값을 구합니다. memo[i][0] += min(memo[i - 1][1], memo[i - 1][2]); memo[i][1] += min(memo[i - 1][0], memo[i - 1][2]); memo[i][2] += min(memo[i - 1][0], memo[i - 1][1]); 이렇게 나타낼 수 있습니..
[C++] 백준 2447번 별 찍기 - 10
별을 찍는 문제입니다. 3의 n제곱으로 입력을 받습니다. 3의 입력값은 다음 모양을 가집니다. ★ ★ ★ ★ ★ ★ ★ ★ 9의 입력값은 다음 모양을 가집니다. ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ ★ 여기서 알 수 있는점은 3은 가운데가 비어있고 나머지를 별로 채운 모양입니다. 9는 3*3모양씩 잘라서 생각했을때 가운데가 비어있고 나머지는 3을 입력했을때의 모양으로 채워져있습니다. 27을 입력한다면 9*9의 모양으로 잘라서 보았을때 가운데가 비어있고 나머지는 9를 입력했을때의 모양으로 채워져 있을것입니다. 이 문제는 ..
[C++] 백준 1669번 멍멍이 쓰다듬기
원숭이가 강아지보다 키가 커질때까지 몇일이 걸리는지 구하는 문제입니다. 원숭이의 키는 그전날에 컸던 키의 -1, 0, +1 cm가 클 수 있습니다. 첫날에는 1cm로 시작하며 마지막날에는 1cm로 끝나야 합니다. ex) 11cm - 6일 1day 2day 3day 4day 5day 6day 7day 8day 9day 10day 1 2 3 2 2 1 X X X X ex) 30cm - 10일 1day 2day 3day 4day 5day 6day 7day 8day 9day 10day 1 2 3 4 5 5 4 3 2 1 ex) 16cm - 7일 1day 2day 3day 4day 5day 6day 7day 8day 9day 10day 1 2 3 4 3 2 1 X X X 1. n*n은 n*2-1(일)입니다. 1*..
[C++] 백준 1947번 선물 전달
n명의 사람이 선물을 한개씩 준비해서 자신이 아닌 사람에게 나누어줄 때 n명의 사람들은 선물을 하나씩 받게 됩니다. (2개 이상 받거나, 안 받을 수 없음) 이 때 줄 수 있는 경우의 수를 구하는 문제입니다. 다이나믹 프로그래밍, 완전 순열 문제입니다. ※ 완전 순열 : n명의 사람이 각각 자신의 모자를 벗어두었다가, 다시 쓰는데 모든 사람이 자기 것이 아닌 모자를 쓰는 방법의 수 1. 1:1로 선물을 교환한 경우 2. 다른 사람에게 하나를 주었을 경우 두 가지가 있습니다. 1번의 경우 1:1로 교환했을 때 다른 남은 사람들은 n-2명입니다. 이는 memo[n-2]의 값을 나타냅니다. 2번의 경우 (1번->2번)에게 선물을 주었을 때 남은 사람들은 n-1명 입니다. 이는 memo[n-1]의 값을 나타냅니..