개발 블로그

문제 링크 : www.acmicpc.net/problem/11722

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

접근 방법

아래 주석과 같다

#include <iostream>
#include <vector>
using namespace std;

int main() {

	int N; cin >> N;
	vector<int> vec;
	vector<int> vecArr[1000];
	int dp[1001] = { 0 };

	for (int i = 0; i < N; i++) {
		int num; cin >> num;
		vec.push_back(num);
	}
	dp[0] = 1;
	vecArr[0].push_back(vec[0]);


	vector<int> longVec = vecArr[0];
	for (int i = 1; i < vec.size(); i++) {

		vecArr[i].push_back(vec[i]);			//일단 처음에 초기화 해 놓고
		dp[i] = 1;

		
		for (int j = 0; j < i; j++) {			//처음부터 해당 차례 직전까지 돌면서 
			if (vec[i] < vec[j]) {				//해당 차례가 더 작으면 이어 붙인다
				if (dp[j] + 1 > dp[i]) {		//대신 dp 갱신 조건을 만족해야만 이어붙인다
					vecArr[i].clear();
					vecArr[i] = vecArr[j];
					vecArr[i].push_back(vec[i]);
					dp[i] = dp[j] + 1;
				}
			}
		}
		

		if (longVec.size() < vecArr[i].size()) {		//매번 가장 긴 수열을 갱신한다
			longVec = vecArr[i];
		}		
	}


	cout << longVec.size();

	return 0;
}

문제 링크 : www.acmicpc.net/problem/11057

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

접근 방법

dp[N][j] : N자리 수 중 j로 끝나는 수의 개수

로 정의하고 경우의 수를 아래 그림과 같이 나열해보니 쉽게 규칙을 찾을 수 있었다.

문제에서 수는 0으로 시작할 수 있다고 했으므로 이를 주의하자.

dp[1][0], dp[1][1],,, dp[1][9]는 모두 한 자리 수에 해당하므로 1로 초기화하고 N=2부터 dp를 구해준다.

#include <iostream>

using namespace std; 


int main() {

	int dp[1001][10];
	for (int i = 0; i <= 1000; i++) {
		for (int j = 0; j <= 9; j++) {
			dp[i][j] = 0;
		}
	}

	for (int i = 0; i <= 9; i++) {
		dp[1][i] = 1;		//한자리수 초기화	
	}
	for (int i = 0; i <= 1000; i++) {
		dp[i][0] = 1;			//0으로 끝나는 오르막 수는 1개
	}

	for (int i = 2; i <= 1000; i++) {
		for (int j = 1; j <= 9; j++) {
			for (int k = 0; k <= j; k++) {
				dp[i][j] += dp[i - 1][k] % 10007;			//더할때마다 MOD 연산 수행
			}
		}
	}


	int N; 
	cin >> N;

	int ans = 0;
	for (int i = 0; i <= 9; i++) {
		ans += dp[N][i];
	}
	cout << ans % 10007;			//마지막 출력할 때도 MOD 연산 후 출력

	return 0;
}

이때 주의할 점은 ans += dp[N][i] % 10007을 하고 마지막에는 그냥 ans 만 출력하면 틀린 답이라고 나온다는 것이다.

(이론상 mod 연산은 분배법칙이 성립해서 (a mod m + b mod m) = (a+b)mod m 를 만족하는데 왜 틀린지 모르겠다.)

문제 링크 : www.acmicpc.net/problem/1149

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

접근 방법

현재 내가 칠할 색을 r,g,b로 각각 세 경우로 나눠서 생각해야한다.

만약 내가 현재 r을 칠한다고 하면, 그 전 집은 g 또는 b로 칠할 수 있다. 

현재 g를 칠한다고 하면, 그 전 집은 r 또는 b로 칠할 수 있다.

현재 b를 칠한다고 하면, 그 전 집은 r 또는 g로 칠할 수 있다.

dp[i][0] 은 i번째 집을 r로 칠하는 경우에, 1~i번째 집을 모두 칠하는데에 드는 최소 비용을 저장하고

dp[i][1] 은 i번째 집을 g로 칠하는 경우에, 1~i번째 집을 모두 칠하는데에 드는 최소 비용을 저장하고

dp[i][2] 은 i번째 집을 b로 칠하는 경우에, 1~i번째 집을 모두 칠하는데에 드는 최소 비용을 저장한다.

문제의 예제로 생각해보자. 아래 표는 dp[][] 이다.

3번째 집을 칠하기까지 최소 비용은 min(96,172,185) = 96이 답이 된다.

처음에는 3가지가 아닌 6가지로 나눠서 생각했었다. (현재 내가 r을 칠하는 경우에 (전에 g, 전전에 b) or (전에 b, 전전에 g) .... 이런식으로) 

그러나 어짜피 dp[i][0]에 값을 저장할 때, i번째에 r을 칠할 때 

1) i-1 번째 g 칠하기

2) i-1 번째 b 칠하기

이렇게 두가지 경우에서 최소 값을 따져서 저장했으므로 6가지로 나눠서 생각할 필요 없이 3가지로만 나눠서 생각하면 되는 것이다.

#include <iostream>
#include <algorithm>

using namespace std;

int rgbArr[1001][3];
int dp[1001][3];

int main(){
    
    int N; cin>>N;

    for(int i = 1; i<=N; i++){
        for(int j = 0; j<=2; j++){
            scanf("%d", &rgbArr[i][j]);
        }
    }
    rgbArr[0][0] = 0;   rgbArr[0][1] = 0;   rgbArr[0][2] = 0;
    dp[0][0] = 0;   dp[0][1] = 0;   dp[0][2] = 0;
    dp[1][0] = rgbArr[1][0];    dp[1][1] = rgbArr[1][1];    dp[1][2] = rgbArr[1][2];

    
    for(int i = 2; i<=N; i++){
        
        dp[i][0] = min(rgbArr[i][0] + dp[i-1][1], rgbArr[i][0] + dp[i-1][2]);
        dp[i][1] = min(rgbArr[i][1] + dp[i-1][0], rgbArr[i][1] + dp[i-1][2]);
        dp[i][2] = min(rgbArr[i][2] + dp[i-1][0], rgbArr[i][2] + dp[i-1][1]);
        
        int mini=1000000; //1000*1000
        for(int j = 0; j<=2; j++){
            mini = min(mini, dp[i][j]);
        }
        
    }
    
    int ans=1000000;
    for(int i = 0; i<3; i++){
        ans = min(ans, dp[N][i]);
    }

    
    cout << ans;
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1463

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

접근 방법

dp[n] 는 n를 1로 만들기까지 필요한 연산 수이다. 

dp[n] = min(dp[n/3], dp[n/2], dp[n-1]) 로 구하는데, 이때 n이 3 또는 2로 나눠지지 않을 경우에는 최소값 후보에서 제외해야한다.

(어떤 수로 초기화해야하는가에 대한 것은 n이 최대(10^6)일 때 n에서 1을 만들기까지 필요한 연산의 최대값으로 초기화해주면 된다. 즉 10^6에서 1씩 빼는 연산으로만 1을 만들때 필요한 연산의 수인 10^6으로 초기화하면 된다. 본인은 혹시 몰라서 그것보다 더 큰수로 초기화했다.)

1부터 9까지 노가다로 구해보자.

그 다음 n=10일때를 생각해보자.

n은 3으로 나눠떨어지지 않으므로

10->5->...

10->9->...

이 두가지 경우를 생각해볼 수 있다.

dp[5] = 3이고 dp[9] = 2이므로 아래 경우로 계산했을 때 최소 연산으로 1을 만들 수 있다.

즉 dp[10] = dp[9] + 1 인 것이다. 

#include <iostream>
#include <algorithm>

using namespace std;

int X;
int ans = 1000000;

int dp[1000001] = {0};

//dp[a], dp[b], dp[c] 중 최소값 리턴
int searchMin(int a, int b, int c){
    
    int min1, min2;
    
    if(dp[a]<dp[b]) {
        min1 = dp[a];
        if(dp[a]<dp[c]) { min2 = dp[a]; }
        else min2 = dp[c];
        
    }
    else{
        min1 = dp[b];
        if(dp[b]<dp[c]) { min2 = dp[b];}
        else min2 = dp[c];
    }
    return min2;
}

int main(){
    
    int X; cin >> X;
    
    //n이 3 또는 2로 나눠지지 않을 때 최소값을 계산하는 searchMin()에서 영향을 주지 않기 위해 큰 수로 초기화한다.
    for(int i = 0; i<1000001; i++){dp[i] = 10000000;}
    
    int fir=0, sec=0, trd=0, mini=0; dp[0] = 0; dp[1] = 0;

    for(int i = 2; i<=X; i++){
        
        fir = i; sec= i; trd = i;
        
        if(i%3 == 0){
            fir = i/3;
        }
        if(i%2 == 0){
            sec = i/2;
        }
        
        trd = i-1;
        
        mini = searchMin(fir, sec, trd);
        dp[i] = mini + 1;
        
    }
    cout << dp[X];
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1912

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

접근 방법

처음에는 DP1[i]를 Arr[0]~Arr[i] 까지 고려했을 때 연속되는 수열의 최대 합을 저장하도록 구현했었다.즉 Arr[i-1] 부터 Arr[0] 까지 거꾸로 가면서 음수가 나오면 그 음수를 수열에 포함할 것인지 아닌지에 따라 경우를 나눠야했다.

아래 표에서 색칠한 부분을 생각해보자. 

i=6일 때, Arr[6] 이 -35로 음수이다. -35를 포함하지 않고 Arr[i] ~ Arr[5] 까지만 더한 21이 최대합을 가지는 수열이다. 이는 i=7일때도 같으며, i=8이 되는 순간 Arr[7] + Arr[8] 을 더한 33이 최대합이 된다. 

이 방법으로 구현했을 때, Arr[i]이 음수인 경우 그 음수만큼 상쇄시켜서 양수로 만들 수 있을 때 까지 Arr[i]을 거꾸로 탐색해가면서 수열에 포함해야할지 따져야 하는데 너무 복잡해져서 다시 DP2[i]를 구하는 방법으로 구현했다.

DP2[i]는 DP1[i] 과 달리 Arr[0]부터 Arr[i] 까지 고려했을 때 최대값을 담고 있지 않다. 그러나 DP2[i]를 채우면서 최대값(ans)을 따로 저장해준다면 

DP2[i]는 DP2[i-1]에다가 Arr[i] 을 계속 더해 나가는 방법이되, 더했는데도 현재 숫자인 Arr[i]보다 작으면 바로 Arr[i]이 원소 한개인 수열이 되도록 하는 것이다.  아래 예시를 들어봤다.

i = 1

10-4 vs -4 = 6

i=2

6+3 vs 3 = 9

i = 3

9+1 vs 10 = 10

i = 4

10+5 vs 5

i = 5

15+6 vs 6

i = 6

21-35 vs -35 = -14

i = 7

-14+12 vs 12 = 12

....

예시들을 아래 코드로 옮겼다.

        DP[i] = max(DP[i-1] + Arr[i], Arr[i]);
        ans = max(ans, DP[i]);

이 코드가 핵심이다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Arr[100001] = {0};
int DP[100001] = {0};

int main(){
    
    
    int N;
    cin >> N;
    int ans;
        
    for(int i = 0; i<=N; i++){ cin >> Arr[i];}
    
    DP[0] = Arr[0];
    ans = Arr[0];
    for(int i = 1; i<N; i++){
        
        DP[i] = max(DP[i-1] + Arr[i], Arr[i]);
        ans = max(ans, DP[i]);
        
    }
    
    cout << ans;
    
    
    return 0;
}

참고 : Arr[i]의 최대 값은 1000이며, N 최대값은 100,000 이다. 즉 Arr[0] ~ Arr[100,000] 에 모두 1000이 저장되어도 int 형의 범위를 넘지 않는다. 그래서 Dp[]는 int 형으로 해도 괜찮다.

문제 링크 : www.acmicpc.net/problem/1699

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

접근 방법1

제곱수를 기준으로 생각했을 때, 항의 개수가 최소가 되려면 그 제곱수를 반드시 포함해야 한다고 생각했다.

예를 들어 18을 제곱수로 나타낸다고 하면, 

16<18<25 이기 때문에 18을 나타내려면 무조건 16이 들어가야한다고 생각했다.

그런데 예외로 18 = 9+9 로 16+1+1 보다 더 짧게 나타낼 수 있었다.

접근 방법 2 

18 을 자연수 2개의 합으로 나타낸다고 했을 때, 그 경우의 수를 모두 검사해서 최소가 될 때를 찾았다.

(1, 17)

(2, 16)

(3, 15)

(4, 14)

(5, 13)

(6, 12)

(7, 11)

(8, 10)

(9, 9) 

그러나 시간 초과가 떴다. 다시 생각해보니 이 중에 최소가 될 수 있는 후보는 제곱수가 포함된 경우였다.

그래서 1,4,9,16이 포함된 경우만 다시 검사해서 최소일 때를 찾아주었다.

즉,

dp[18-1] + dp[1]  => (16+1)+1

dp[18-4] + dp[4] =>  (9+4+1)+4

dp[18-9] + dp[9]  => 9 + 9

dp[18-16] + dp[16] => (1+1)+16

#include <iostream>
#include <algorithm>

using namespace std;

int dp[100489] = {0};

int main(){
     for(int i = 1; i<=100000; i++){
         dp[i] = 10000;
     }
    
    int N;
    cin >> N;

    dp[0] = 0; dp[2] = 2; dp[3] = 3;
    for(int i = 1; i*i<=100000; i++){
        dp[i*i] = 1;
    }
    
    for(int i = 1; i<=316; i++){
        for(int j = i*i+1; j<=(i+1)*(i+1)-1; j++){
            for(int k = 1; k<=i; k++){
                dp[j] = min(dp[j], dp[j-k*k] + dp[k*k]);
            }
        }
    }

        cout << dp[N];

    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/15990

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

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

입력

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

출력

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

접근 방법

문제의 조건에서 유의해야 할 점이 있다.

1) 1+3과 3+1 이 다름.

2) 같은 수를 두 번 이상 연속해서 사용할 수 없음.

일단 규칙을 찾기 위해 쭉 써보았다.

dp[1] = 1 (1)  (단일 숫자)

dp[2] = 1 (2) (단일 숫자)

dp[3] = dp[2]에 1을 더하는 경우 (2+1 -> 1가지)

          + dp[1]에 2를 더하는 경우 (1+2 -> 1가지)

          + dp[0]에 3을 더하는 경우 (0+3 -> 1가지)

          = 1 + 1 + 1 =3 

dp[4] = dp[3]에 1을 더하는 경우 (1+2+1 , 0+3+1 -> 연속 제외하고 2가지)

          + dp[2]에 2를 더하는 경우 (연속 제외하고 0가지)

          + dp[1]에 3을 더하는 경우 (1+3 -> 1가지)

          = 2 + 0 + 1 = 3

dp[5] = dp[4]에 1을 더하는 경우 (1+3+1 -> 연속 제외하고 1가지)

          + dp[3]에 2를 더하는 경우 (2+1+2, 0+3+2 -> 연속 제외하고 2가지)

          + dp[2]에 3을 더하는 경우 (2+3 -> 1가지)

          = 1 + 2 + 1 = 4

dp[6] = dp[5]에 1을 더하는 경우 (2+1+2+1, 0+3+2+1, 2+3+1 -> 연속 제외하고 3가지)

          + dp[4]에 2를 더하는 경우 (1+2+1+2, 0+3+1+2, 1+3+2 -> 3가지)

          + dp[3]에 3을 더하는 경우 (2+1+3, 1+2+3 -> 연속 제외하고 2가지)

          = 3 + 3 + 2 = 8

dp[7] = dp[6]에 1을 더하는 경우 (1+2+1+2+1, 0+3+1+2+1, 1+3+2+1  / 2+1+3+1, 1+2+3+1 -> 연속 제외하고 5가지)

          + dp[5]에 2를 더하는 경우 (1+3+1+2, 2+3+2 -> 연속 제외하고 2가지)

          + dp[4]에 3을 더하는 경우 (1+2+1+3, 0+3+1+3 -> 연속 제외하고 2가지)

          = 5 + 2 + 2 = 9

dp[n] = arr1[n] + arr2[n] + arr3[n] 으로 분할해서 더한다고 하자. (RHS의 각 배열은 +1, +2, +3 하는 경우이다.)

그러면

arr1[n] = arr2[n-1] + arr3[n-1]

arr2[n] = arr1[n-2] + arr3[n-2]

arr3[n] = arr1[n-3] + arr2[n-3] 

인 규칙을 찾을 수 있다. (위에 색칠해놓은 글씨를 보면 이해하기 쉽다.)

#include <iostream>

using namespace std;

long long dp[100001] = {0};
long long arr1[100001] = {0};
long long arr2[100001] = {0};
long long arr3[100001] = {0};


int main(){
    
        
    int TC; cin >> TC;

    arr1[3] = 1;    arr1[4] = 2;    arr1[5] = 1;
    arr2[3] = 1;    arr2[4] = 0;    arr2[5] = 2;
    arr3[3] = 1;    arr3[4] = 1;    arr3[5] = 1;
    
    dp[0] = 1; dp[1] = 1; dp[2] = 1;
    for(int i = 3; i<=5; i++) {dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;}
    
    for(int i = 6; i<=100000; i++){
        arr1[i] = (arr2[i-1] + arr3[i-1]) % 1000000009;
        arr2[i] = (arr1[i-2] + arr3[i-2]) % 1000000009;
        arr3[i] = (arr1[i-3] + arr2[i-3]) % 1000000009;
        dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;
    }
    
    
    for(int t = 0; t<TC; t++){
        
        int n;
        cin>>n;
        
        cout << dp[n] << "\n";
        
        
    }
    
    
    return 0;
}

주의할 점

int 형은 더할 때 범위가 넘어가므로 long long 자료형을 사용해야 한다.

그리고 for 문 안에서 arr1[], arr2[], arr3[] 을 구할 때도 Mod 연산을 적용해서 저장해야 한다. 

문제 링크 : www.acmicpc.net/problem/11052

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

접근 방법 1) 

dfs로 풀었는데 역시 시간초과가 떴다 .

#include <iostream>
#include <vector>

using namespace std;

int N;
int P[1001] = {0};
vector<int> vec;
int maxSum = 0;

void dfs(int sum, int idx){
    
    if(sum>N) return;
    
    if(sum==N){
        int ans=0;
        for(int i=0; i<vec.size(); i++){
            ans += vec[i];
        }
        if(maxSum<ans){maxSum = ans;}
        
        
        return;
    }
    for(int i = 1; i<=N; i++){
        
        if(idx<=i){
            sum+=i;
            vec.push_back(P[i]);
            dfs(sum, i);
            sum-=i;
            vec.pop_back();
        }
    }
}

int main(){
    
    
   
    cin >> N;
    for(int i = 1; i<=N; i++){
        cin >> P[i];
    }
    dfs(0,0);
    cout << maxSum;
    
    
    
    return 0;
}

접근 방법 2)

 dp로 풀어야 시간 안에 문제를 풀 수 있을 것이다.

먼저 N = 3일 때, 어떤 카드팩 조합이 최대 금액이 될 것인가?

dp[n] 을 n개의 카드를 구매하는데에 필요한 최대 금액이라고 하자.

그러면 dp[3] 은 

dp[3-1] + P[1]

dp[3-2] + P[2] 

dp[3-3] + P[3]  (카드 팩 1개 통째로 사는 경우)

중 가장 큰 값이 될 것이다. 이는 아래와 같이 나타낼 수 있다. 

for(int j = 1; j<=i; j++){

      dp[i] = max(dp[i], dp[i-j] + P[j]);

}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int P[1001] = {0};
int dp[1001] = {0};
vector<int> vec;
int maxSum = 0;



int main(){
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        cin >> P[i];
    }

    dp[0] = 0;
    dp[1] = P[1];
    
    for(int i = 2; i<=N; i++){
        for(int j = 1; j<=i; j++){
            dp[i] = max(dp[i], dp[i-j] + P[j]);
        }
    }
    
    cout<<dp[N];
    
    return 0;
}