7주차: DP(Dynamic Programming) , 2240번: 자두 나무, 15989번: 1, 2, 3 더하기 4

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의

https://blog.naver.com/jhc9639/222349317111

[알고리즘 강의] 7주차. DP, 동적계획법, 다이나믹프로그래밍

 

수업을 듣고 정리한 글입니다.

 

DP 

만들어진 점화식을 기반으로 문제를 풀어야한다.

점화식을 만들때는 완전탐색+메모이제이션(배열 등에 저장)을 생각한다.

 

메모이제이션

상태값을 자료구조에 저장해두어 다시 한번 계산하는 것을 막는다.

저장된 값을 사용한다.

 

DP의 조건

1. 참조 투명성 => 코딩 테스트라면 다 지켜서 줌

2. 겹치는 부분 문제 (피보나치 수열)

3. 최적 부분구조 : 지금의 최적해가 결과적으로 글로벌한 최적해가 되는 것

 

DP 판단 방법

1. 완전탐색의 경우 => 2. 경우의 수가 너무 큰 경우 => 3. 메모이제이션 가능한 경우 => DP

 

dp에서 함수는 무조건 return 타입이 있어야한다.(void 안됨)

 

DP 

초기화 + 기저 조건(종료 조건) + 메모이제이션(저장 가능 여부) + 로직(리턴값)

 

 

2240번: 자두 나무

자두나무

 

시간 제한         메모리 제한        제출        정답        맞힌 사람        정답 비율

2 초

128 MB

12543

4392

3218

37.423%

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

 

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

 

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

예제 입력 1 복사

7 2
2
1
1
2
2
1
1

예제 출력 1 복사

6

 

https://www.acmicpc.net/problem/2240

2240번: 자두나무

 

선생님 코드

#include <bits/stdc++.h>
using namespace std;

int t,w,a[1004],dp[1004][2][34]; //자두 떨어지는 초, 트리 위치, 최대 움직일수있는 횟수

int go(int idx, int tree, int cnt){
    //기저사례
    if(cnt<0) return -1e9; //움직일 수 없으면
    if(idx==t) return 0; //
     //메모이제이션
    int &ret = dp[idx][tree][cnt];
    if(~ret) return ret; //~a=-(a+1), 음수가 아니면 ret 리턴
    //로직
    return ret = max(go(idx+1,tree^1,cnt-1), go(idx+1,tree,cnt)) + (tree==a[idx]-1); //max(움직이거나, 움직이지않거나) + 사과개수
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    memset(dp,-1,sizeof(dp)); //dp 원소들을 -1로 초기화
    //1. 입력받기
    cin >> t >> w;
    for(int i=0;i<t;i++) cin >> a[i];
    //2. dp 수행(트리 0부터 시작)
    cout << max(go(0,0,w), go(0,1,w-1)) << "\n"; //움직이지않거나, 움직이기

}

 

코드 설명

• 완전탐색인데 경우의 수는 2^30..이므로 dp를 사용한다.
• 3가지 키워드 : 현재 시간(T), 트리 위치, 이동횟수 => dp[1004][2][34]
• 트리위치는 배열 2로 선언했기때문에 0이면 트리 1을, 1이면 트리2를 가리킨다.
• dp를 수행하는 go에서 return 코드를 보면

return ret = max(go(idx+1,tree^1,cnt-1), go(idx+1,tree,cnt)) + (tree==a[idx]-1); //max(움직이거나, 움직이지않거나) + 사과개수

움직이거나, 움직이지 않을때의 max 결과값을 구하고, 현재 사과위치와 내 위치가 같으면 +1(True)를 해준다.

같은 위치일때 사과 +1

 

 

• 최대값을 구하므로 맞지 않은 경우의 수는 -1e9(1000000000)=10억을 해준다.
• ret과 리턴값 꼭 쓰기!

 

15989번: 1, 2, 3 더하기 4

 

시간 제한          메모리 제한          제출          정답          맞힌 사람          정답 비율

1 초 (추가 시간 없음)

512 MB

5296

3340

2640

64.234%

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1 복사

3
4
7
10

예제 출력 1 복사

4
8
14

 

 

• 경우의 수는 다 더하면 된다.

선생님 코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll t,n,dp[10004];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> t;
    //2. 합 만들기
    dp[0]=1; //초기값
    for(int i=1;i<=3;i++){ //1,2,3
        for(int j=1;j<=10000;j++){ //만들 숫자
            if(j-i>=0){
                dp[j]+=dp[j-i]; //dp[j-i]의 경우의 수에서 +i하는 경우의수 +1
            } 
        }
    }
    //3. 정답 출력
    while(t--){
        cin >> n;
        cout << dp[n] << "\n";
    }
}

 

피보나치 수 2 

성공다국어

한국어   

시간 제한         메모리 제한         제출         정답         맞힌 사람         정답 비율

1 초

128 MB

85217

34685

28475

40.299%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

 

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1 복사

10

예제 출력 1 복사

55

 

유의할 점

• 피보나치 수는 굉장히 커지므로 long long 타입으로 선언하자
• 메모이제이션을 이용하여 속도를 빠르게 하자.

내 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, dp[100];

ll fibo(int n){
    if(n==0||n==1) return n;
    ll &ret = dp[n]; 
    if(ret) return ret; //값 존재하면 리턴
    return ret=fibo(n-1)+fibo(n-2); //존재하지않으면 계산
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    //2. fibo 수행하기
    cout << fibo(n) << "\n";
}