Storage Gonie

포도주 시식 문제 - https://www.acmicpc.net/problem/2156 문제요약 포도주가 일렬로 놓여져 있고, 다음과 같은 2가지 규칙을 지키면서 포도주를 최대한 많이 마시려고 한다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 2. 연속적으로 놓여 있는 3잔을 모두 마실 수는 없다. 해결 방법1 (2차원 배열) 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "A[1]~A[N] 즉, N개의 포도주가 있을 때 가장 최대로 마실 수 있는 양" D[N][S] = "N개의 포도주 잔이 있고, N번째 포도주 잔의 상태가 S일 때 가장 최대로 마실 수 있는 양" S는 3가지 상태일 수 있..

스티커 문제 - https://www.acmicpc.net/problem/9465 문제요약 2xn 모양으로 놓여진 스티커가 있는데 각각의 스티커는 점수를 가지고 있다. 한장을 뗄 때마다 변을 공유하는 상하좌우의 스티커는 찢어져서 사용할 수 없게된다. 이때 떼어낸 스티커 점수들의 합의 최대값을 출력하시오. 해결 방법 무조건 큰 수부터 뜯어내면 최대합을 만들 수 있을까? 정답은 X 이다. 아래의 2x3 모양의 스티커 예시를 보자. 99 100 99 1 99 1 가장 큰 수인 100을 뜯어내면 합은 100 + 1 + 1 = 102이고, 99를 뜯어낸다고 하면 99 + 99 + 99 = 297이다. 따라서 최대합을 만들기 위해 무조건 큰 수 부터 떼네는 것은 옳지 않다. 위의 이유로 뜯는 순서가 정해져 있지 않..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-9-DP-문제-풀이8-백준-No11057-오르막-수 # C++(Bottom-up방식) #include using namespace std; int d[1001][10]; int main() { int n; cin >> n; // d[1][0~9], "길이가 1이고 0~9로 끝나는 수"에 대한 값 초기화 for (int i = 0; i

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-8-DP-문제-풀이6-백준-No10844-쉬운-계단-수?category=864321 # C++(Bottom-up방식) #include using namespace std; int d[101][10]; int main() { int n; cin >> n; // n이 1일 때 결과가 9이므로 해주는 초기화 for (int i = 1; i

다이나믹 프로그래밍 문제 * 다이나믹 문제만이 가지고 있는 패턴을 익히기 위해 많은 문제를 풀어보는 것이 중요함 1. 결과를 특정한 수로 나눈 나머지를 출력하라는 유형의 문제 - 접근 방법 : 최종 연산된 결과에만 나머지 연산을 수행하면 안되고, 값을 계산할 때 마다 d 배열에 나머지를 저장해야함. 그 이유는 출제자가 이미 중간 연산의 결과가 데이터의 저장범위를 넘어가는 것을 알고 있기에 이런 문제를 내는 것이고, 이렇게 해주지 않으면 의도된 답을 구할 수 없게 된다. 2. 2차원 이상의 배열을 사용해야하는 유형의 문제 - 접근 방법 : 점화식을 만들고 구현하는 것은 1차원 배열을 사용하는 문제와 동일하니, 1차원 배열로 풀어야하는지 2차원 배열로 풀어야 하는지 판단하는 능력을 길러야 한다. 1차원 배열..

문제 풀이 자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-7-DP-문제-풀이6-백준-No0000-카?category=864321 # C++(Top-down방식) #include using namespace std; long long d[91] = {0}; long long getTwoChinNum(int n) { if ( n 0) return d[n]; else d[n] = getTwoChinNum(n-1) + getTwoChinNum(n-2); return d[n]; } int main() { int n; cin >> n; d[1] = 1; d[2] = 1; cout > n; d[1] = 1; d[2] = 1; for (int i=3; i

오르막 수 문제 - https://www.acmicpc.net/problem/11057 문제요약 '오르막 수'는 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. ex) 2234, 3678, 1119 수의 길이 N이 주어졌을 때, '오르막 수'의 개수를 구하는 프로그램을 작성하시오. 출력은 10007로 나눈 나머지 값을 출력하시오. 해결 방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "길이가 N인 오르막 수의 개수" 수의 각 자리에는 0 ~ 9가 올 수 있기 때문에 좀 더 세분화 할 수 있도록 2차원 배열로 다음과 같이 정의해준다. D[N][L] = "길이가 N이고 수 L으로 끝나는 오르막 수의 개수" 2. D[N]의 값을 ..

쉬운 계단 수 문제 - https://www.acmicpc.net/problem/10844 문제요약 정수 N이 주어지는데 인접한 자리의 수 차이가 모두 1인 수를 '계단 수' 라고 칭한다. ex) 45656 길이가 N인 계단 수의 개수를 구하고 1000000000로 나눈 나머지를 출력하라. 해결 방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N][L] = "L로 끝나는 길이가 N인 '계단 수' 의 개수" - 이전 문제에서는 0 또는 1만 왔는데, 여기는 한 자리에 0~9가 올 수 있기 때문에 1차원으로 문제를 풀 수 없다. 따라서 2차원 배열을 활용하게 된다. 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지고, 앞에 어떤 조합이..

ㅇㅇㅇ 문제 - 문제요약 해결 방법 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N개를 모두 구매하며 지불할 수 있는 최대 금액" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다. 3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임. - 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다. (Overlapping SubProblem) - 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 ..

이친수 문제 - https://www.acmicpc.net/problem/2193 문제요약 2진수에서 다음 두 조건을 만족하면 이친수라고 한다. 1) 0으로 시작하지 않는다. 2) 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열을 갖지 않는다. 위의 조건을 만족하는 N자리 이친수를 구하는 문제 해결 방법1 (1차원 배열) * 기존에 해오던 방법과 새로운 방법이 있는데 두 번째의 새로운 방법이 더욱 와닿는 방법이라고 할 수 있다. 1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다. - D[N] = "N자리 이친수의 개수" 2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다. - 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다. case1) N번..