개발 블로그

문제 링크 : 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/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;
}

문제 링크 : www.acmicpc.net/submit/11727/26381160

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

접근 방법

가로의 길이가 1부터 n이 될 때까지 타일을 붙여나가며, 이때 두가지 케이스로 나눠서 경우의 수를 카운트했다.

붙여야하는 타일의 가로 길이가 1인 것과 2인 것을 나눴다.

Case 1) 가로 길이가 1인 타일을 붙여야 하는 경우

이 경우는 타일의 길이가 n-1가 되도록 붙이는 경우의 수와 같다. 길이가 n인 타일을 만드려면 n-1 타일에 2x1 타일을 추가하기만 하면 되기 때문이다.

Case 2) 가로 길이가 2인 타일을 붙여야 하는 경우

이 경우엔 두가지 경우로 또 나눠서 생각해야한다. 

2-1) 1x2 타일을 붙이는 경우(세로로 두개)

이 경우는 타일의 길이가 n-2가 되도록 붙이는 경우의 수와 같다. 길이가 n인 타일을 만드려면 n-2 타일에 1x2 타일 두개를 세로로 추가하기만 하면 되기 때문이다.

2-2) 2x2 타일을 붙이는 경우 

이 경우도 2-1과 같다. 2x2 타일을 추가만 하면 된다.

Case 1, 2를 조합해서 생각하면, 길이 n인 타일을 붙이는 경우의 수는,

길이 n-1인 타일을 붙이는 경우의 수 + 2*(길이 n-2인 타일을 붙이는 경우의 수) 로 나타낼 수 있다.

즉, dp[n] = dp[n-1] + 2*dp[n-2]인 것이다.

#include <iostream>
#include <vector>

using namespace std;

int dp[1001] = {0};

int main(){
    
    int n;
    cin >> n;
    
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 3;
    
    for(int i = 3; i<=n; i++){
        dp[i] = (2*dp[i-2] + dp[i-1]) % 10007;
    }
    cout << dp[n];
    
    return 0;
}

이때 주의할 점은 for문 안에서 dp[n] = dp[n-1] + 2*dp[n-2] 로 계산을 쭉 하고

마지막에 출력할 때 dp[n]%10007 을 하면 안된다는 것이다. 위의 코드와 같이 for문 안에서 나머지 계산을 해줘야한다.

문제 요구조건 자체가 mod 연산을 한 결과를 출력하라고 했으니, 처음에 dp[]에 값을 저장할 때 mod연산의 결과를 저장해야한다.