Storage Gonie

카드 구매하기 문제 - https://www.acmicpc.net/problem/11052 문제요약 카드 N개를 구매하려고 하는데, i개를 묶어서 파는 카드 묶음의 가격이 P[i]일 때, N개를 구매하며 지불할 수 있는 최대금액 구하기 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N개를 모두 구매하며 지불할 수 있는 최대 금액" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다. N = O+O+O+...+O+A Case1) 마지막 A에서 1개가 묶어진 것을 지불하고 사는 경우 - 지불할 수 있는 최대 금액은 D[N] = D..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-5-다이나믹-프로그래밍-문제-풀이4?category=864321 # C++(Top-down 방식) #include using namespace std; int d[12] = {1, 1, 2}; // d[0] = 1, d[1] = 1, d[2] = 2, d[4~11] = 0 // d[0] = 1; d[3] = 3인데 이게 정상적으로 작동하려면 d[0]=1이어야 하므로 // d[1] = 1; 원래 d[1]은 1이라서. // d[2] = 2; 원래 d[2]은 2이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >..

1, 2, 3 더하기 문제 - https://www.acmicpc.net/problem/9095 문제요약 정수 N이 주어지면 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N을 1, 2, 3의 합으로 나타내는 방법의 수" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지면 마지막 자리에 3가지 방법 중 1가지를 선택할 수 있다. N = O+O+O+...+O+O+A Case1) 맨 뒤 A자리에 1을 조합으로 추가하는 경우 - 1을 조합으로 추가했으므로 N-1을 1, 2, 3의 조합으로 나타내는 것을 다시 찾아내면 됨. Case2) 맨 뒤 A자리에 2을 조합으로 ..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-4-다이나믹-프로그래밍-문제-풀이3 # C++(Top-down방식) #include using namespace std; int d[1001] = {1, 1}; // d[0] = 1, d[1] = 1, d[0~99] = 0 // d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함. // d[1] = 1; 원래 d[1]은 1이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[n..

2xn 타일링2 문제 https://www.acmicpc.net/problem/11727 문제요약 2xn 직사각형을 2x1과 2x2 타일로 채워넣는 모든 방법의 수를 구하고, 이를 10007로 나눈 나머지를 출력해라 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지" -> "2 x N 직사각형을 채우는 모든 방법의 수" 로만 일단 생각하자. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 2 x N의 직사각형이 주어지면 마지막 위치에 3가지 방법 중 1가지를 선택할 수 있다. Case1) 세로로 1개를 놓는 경우 - 나머지 2 x (n-1) 크기의 직사각형을 채워넣..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-3-다이나믹-프로그래밍-문제-풀이2 # C++(Top-down 방식) #include using namespace std; int d[1001] = {1, 1}; // d[0] = 1, d[1] = 1, d[0~99] = 0 // d[0] = 1; 이 문제에서 점화식이 정상적으로 작동하려면 d[0]이 1이어야함. // d[1] = 1; 원래 d[1]은 1이라서. // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getAllCombiCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[..

2xn 타일링 문제 https://www.acmicpc.net/problem/11726 문제요약 2xn 크기의 직사각형을 1x2, 2x1 타일로 채워넣는 모든 방법의 수를 구하고, 이를 10007로 나눈 나머지를 출력해라 해결방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지" -> "2 x N 직사각형을 채우는 모든 방법의 수" 로만 일단 생각하자. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 2 x N의 직사각형이 주어지면 마지막 위치에 2가지 방법 중 1가지를 선택할 수 있다. Case1) 세로로 1개를 놓는 경우 - 나머지 2 x (n-1) 크기의 직사각형을 ..

문제 풀이 - 자세한 설명 : https://ldgeao99.tistory.com/entry/챕터3-2-다이나믹-프로그래밍2 # C++(Top-down방식) #include using namespace std; int d[1000000] = {0}; // 1에서 1로 가는건 연산을 필요로 하지 않으므로 d[1] = 0, 그냥 모두 d[0~99] = 0 // N을 1로 만드는데 필요한 최소 연산횟수를 반환하는 함수 int getSmallestCalCount(int n) { if (n 0) // n >= 2 경우, d[n] > 0 이면 이미 계산된 결과가 있음을 의미하므로 바로 결과반환 return d[n]; else { // 모든 수에서 가능한 연산인 -1을 먼저 해준다. d[n] = getSmallest..

1로 만들기 문제 https://www.acmicpc.net/problem/1463 문제요약 어떤 정수 N에 대해 다음과 같은 연산중 하나를 선택할 수 있다. 1) 3으로 나누어 떨어지면 3으로 나눈다. 2) 2로 나누어 떨어지면 2로 나눈다. 3) 1을 뺀다. 이를 반복하여 1을 만들려고 하는데 연산을 사용하는 횟수의 최소값을 출력해라. 해결방법 - 다른 문제에도 공통적으로 적용됨 1. D[N]에 어떤 값을저장할 것인지 문장으로 정의해줘야 한다. - 대부분의 다이나믹 문제는 문제에서 구하라는 값을 그대로 D[N]에 넣어주면 된다. - 따라서, D[N]= "정수 N을 1로 만드는데 필요한 연산 횟수의 최소값" 이라고 정의해 줄 수 있다. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다...

# 배열 선언방법 @ 정적배열 // N * M 행렬 int arr[3][5]; // N * M 행렬 int arr[3][5] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}}; // 배열 선언시 왼쪽인자를 생략할 수 있음. (오른쪽 인자는 생략 불가, 둘다 생략하는 것도 불가) int arr[][5] = {{1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {11, 12, 13, 14, 15}}; @ 동적배열 - 아직까진 사용할 일이 없었어서 학습 보류(동적할당이 필요한 이유 포함) // 1차원 배열 할당받는 방법 int width = 8; int *arr; arr = (int *) malloc ( sizeof(int) * width )..