차근차근

0. 제목 백준 2225 합분해 BOJ 2225 합분해 C++ 2225 합분해 1. 문제 https://www.acmicpc.net/problem/2225 2. 풀이 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다. dp를 이용하였고 dp[K][N]의 의미는 K개의 수로 N을 만드는 경우의 수이다. 예를 들어, dp[3][30]을 구한다고 해보자. 3개로 30을 만들어야 하는 경우이고, 마지막에 더하는 수가 0이라면 2개로 30을 만드는 경우가 나올테고, 마지막에 더하는 수가 1이라면 2개로 29를 만드는 경우가 나올테고, 마지막에 더하는 수가 2라면 2개로 28을 만드는 경우가 나올테다. 위와 같이 쭉 나열해보면 다음과 같은 점화식이 나온다. dp[i][j] = dp..

0. 제목 백준 9461 파도반 수열 BOJ 9461 파도반 수열 C++ 9461 파도반 수열 1. 문제 https://www.acmicpc.net/problem/9461 2. 풀이 점화식을 찾으면 쉽게 풀리는 문제이다. 두가지 점화식으로 풀리는데 다음과 같다. dp[i] = dp[i-2] + dp[i-3] dp[i] = dp[i-1] + dp[i-5] 두가지 중 하나로 코드를 짜면 정답이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using namespace std; int main(int argc, const char * argv[]) { int T, N; long int dp[101] = {0}; cin >> ..

0. 제목 백준 1003 피보나치 함수 BOJ 1003 피보나치 함수 C++ 1003 피보나치 함수 1. 문제 https://www.acmicpc.net/problem/1003 2. 풀이 dp방식을 사용하였다. dp[i][0]은 i 번째 수 계산 시 나오는 0의 개수이고 dp[i][1]은 1의 개수이다. i가 0, 1일때 초기값을 지정해주고 dp[i][k] = dp[i-1][k] + dp[i-2][k] 를 수행해주면 0과 1의 개수를 구할 수 있다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int main(int argc, const char * argv[]) { int..

0. 제목 백준 14501 퇴사 BOJ 14501 퇴사 C++ 14501 퇴사 1. 문제 https://www.acmicpc.net/problem/14501 2. 풀이 dp방식을 사용하였으며 dp배열의 원소값을 0으로 모두 초기화 하고 시작하였다. 만약 일을 진행하는데 주어진 날보다 초과되면 dp[i+1] 값을 해주면 된다. 초기에 0으로 초기화해주었기 때문에 N이 초과되어도 0으로 갱신이 가능하다. 주어진 날 내에 끝낼 수 있다면 dp[i] = max(dp[i+T[i]] + P[i], dp[i+1]); 을 수행해준다. 위 점화식을 풀어 설명해보면 dp[i+T[i]]+P[i] 는 i번째 상담을 수행하면 T[i]일간 상담을 못하고 P[i]의 금액을 얻을 수 있고, dp[i+1]은 i번째 상담을 수행하지 않..

0. 제목 백준 1932 정수 삼각형 BOJ 1932 정수 삼각형 C++ 1932 정수 삼각형 1. 문제 https://www.acmicpc.net/problem/1932 2. 풀이 합이 최대가 되는 경로에 있는 수의 합을 출력하는 것이 문제이다. 2차원 배열 arr, dp를 할당하고 arr는 각 위치의 값이 담기고 dp는 그 위치로 갔을 때의 합이 담긴다. 그런데 합이 최대가 되어야 하므로 전 단계에서 즉, 윗 줄에서 왼쪽과 오른쪽중 큰 것을 선택해야 한다. 따라서 점화식은 다음과 같다. dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j] 그런데 좌표를 arr[1][1] 부터 시작하도록 설정하였으며 i-1 이 0이 나오는 dp[i][0]들은 0으로 초기화 시켜..

0. 제목 백준 1010 다리 놓기 BOJ 1010 다리 놓기 C++ 1010 다리 놓기 1. 문제 https://www.acmicpc.net/problem/1010 2. 풀이 mCn을 묻는 문제이다. dp방식을 이용하여 값을 저장해놓는다. dp[i][j]의 값은 왼쪽에 i개, 오른쪽에 j개가 있을 때 연결 방법의 개수이다. 왼쪽에 3개, 오른쪽에 5개가 있다고 가정해보자. 왼쪽의 가장 위에 것이 오른쪽 가장 위로 가면 나올 수 있는 방법 수는 dp[i-1][j-1] 이 된다. 왼쪽의 가장 위에 것이 오른쪽 두번 째로 가면 나올 수 있는 방법 수는 dp[i-1][j-2] 이 된다. 이렇게 쭉 반복하면 2차원 인덱스의 값은 j-1, j-2, ..., i-1 가 가능하다. 점화식을 써보면 다음과 같다. dp..

0. 제목 백준 2133 타일 채우기 BOJ 2133 타일 채우기 C++ 2133 타일 채우기 1. 문제 https://www.acmicpc.net/problem/2133 2. 풀이 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구하는 것이다. 앞서 풀었던 타일 채우기 문제와는 살짝 달랐다. 앞에서 풀었던 타일 문제들은 N의 값이 늘어날 때 새로운 종류의 타일 모양이 나오지 않았다. 그러나 이 문제는 N이 2씩 늘어날때마다 새로운 모양 2개가 추가적으로 생겼다. 먼저 끝 2칸을 제외하면 3가지 방법이 나온다. 그리고 4칸, 6칸, 8칸.... 제외하면 2가지씩 추가적으로 생긴다. 그리고 3xN의 크기의 벽을 2x1, 1x2로 채우기 위해서는 N이 짝수이어야 한다. N이 홀수이면 넓..

0. 제목 백준 1699 제곱수의 합 BOJ 1699 제곱수의 합 C++ 1699 제곱수의 합 1. 문제 https://www.acmicpc.net/problem/1699 2. 풀이 dp방식을 사용하였다. 먼저 dp의 각 원소들을 1로만 이루어진 개수로 초기화시켰다. 이중반복문에서 i와 j는 1부터 시작할 필요가 없다. 이유는 dp[i] = i 여기서 초기화를 했는데 모두 1로 이루어진 경우를 나타낸 것이다. 따라서 2부터 시작해도 상관이 없다. 오히려 더 빠르다. dp[i] = min(dp[i], dp[i-j*j] + 1); 이 부분은 dp[i] 즉, 초기에 설정했던 값과 dp[i-j*j]+1 중 최솟값을 고르는 것이다. dp[i-j*j] 에 1을 더해주는 이유는 j*j에서 항이 1개 나오기 때문이다...

0. 제목 백준 1149 RGB거리 BOJ 1149 RGB거리 C++ 1149 RGB거리 1. 문제 https://www.acmicpc.net/problem/1149 2. 풀이 이웃끼리는 같은 색을 칠할 수 없다. RGB를 각각 0번, 1번, 2번 색이라 하겠다. 0번색을 칠하면 이웃집은 1, 2가 가능하고 1번색을 칠하면 이웃집은 0, 2가 가능하고 2번색을 칠하면 이웃집은 0, 1이 가능하다. arr[i][j]은 i번째 집에 j번 색으로 칠하는 비용이다. dp배열의 초기값으로 첫번째 집의 비용을 설정해주었다. 그 다음부터 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0] 와 비슷한 방식으로 1이면 0,2, 2이면 0,1로 설정하여 실행하였다. 그렇게 마지막 N..

0. 제목 백준 2579 계단 오르기 BOJ 2579 계단 오르기 C++ 2579 계단 오르기 1. 문제 https://www.acmicpc.net/problem/2579 2. 풀이 DP 방식을 이용하였다. [백준 2156] 포도주 시식 문제와 비슷하다. 먼저 초기값인 dp[1], dp[2], dp[3] 을 먼저 설정해준다. 문제에서 계단을 오를때 항상 마지막 계단을 밟아야 한다고 나와있다. 마지막 계단을 i번째 계단이라고 놓으면 i-1 번째 계단과 i-2 번째 계단을 밟는 경우를 생각해봐야 한다. i-1 번째 계단을 밟을 경우 3개 연속으로 밟으면 안되므로 i-2번째는 밟을 수 없다. 따라서 dp[i-3] + arr[i-1] + arr[i] 가 된다 i-2 번째 계단을 밟을 경우는 그대로 dp[i-2]..