JArchive 프로그래밍 일기

문제

가장 긴 증가하는 부분 수열 백준 11053번

리뷰

자신보다 작은 숫자의 개수를 세는 것이 핵심이다.

예시 배열 A = [10 , 20 , 10 , 30, 20 , 50] 이고 크기는 6이다.

입력 배열은 A[i] 에 인덱스 1부터 저장된다. 길이는 6이니까 A[1] ~ A[6] 까지 숫자가 저장되어 있다.

바깥 for문 i 를 기준으로 (자기자신 A[ 1 ] ) 자신보다 작은 숫자의 개수를 센다.

D[ i ] 배열에 A[ i ] 보다 작은 숫자의 개수를 저장한다.

D[i] 값은 안쪽 for문에 들어가기 전에 1로 초기화 된다. (자기 자신의 길이는 1이기 때문이다. )

    for(i = 1; i <= len; i++){

        D[i] = 1; // 자기자신 길이 1 로 초기화 

        for(j = 0; j <= i; j++){
            if(A[i] > A[j]){
                D[i] = max(D[i], D[j] + 1);
            }
        }
        cnt = max(cnt, D[i]); // 여태 까지 구한 D 배열의 최대값을 기억한다. (답으로 출력)
    } 

예를 들어, i = 2 라면, A[2] 값 20 을 기준으로, A[0] , A[1] , A[2] 의 값을 비교한다.

A[2] > A[1] 인 경우에 if 문에 들어가게 된다. (현재 D[2] 값은 1이다. )

D[2] = max( D[ 2 ] , D[ 2 ] + 1)

​ = max ( 1, 2 )

D[2] = 2 이렇게 저장되고 끝나게 된다.

i = 3 이라면, A[3] 값 10을 기준으로 A[0] , A[1] , A[2] , A[3] 과 비교한다.

처음에 D[3] 값은 1이다.

그렇지만 10보다 작은 값이 없으니까 if문에 들어갈 일이 없다. if 문에 들어가지 못하고 종료된다.

A [ 4 ] 의 경우를 보자. A[4] 값 30을 기준으로 A[0] , A[1] , A[2] , A[3] , A[4 ] 값을 비교한다.

처음에 D[4] 값은 1이다.

if (30 > A[0]) 문을 만족한다. A[0] = 0이다.

D[4] = max ( D[4] , D[0] + 1) 이니까 D[4] = 1 이다.

if (30 > A[1]) 문을 만족한다. A[1] = 10 이다.

D[4] = max ( D[4] , D[1] + 1) 이니까 D[4] = 2 이다.

if (30 > A[2]) 문을 만족한다. A[2] = 20 이다.

D[4] = max ( D[4] , D[2] + 1) 이니까 D[4] = 3 이다.

if (30 > A[3]) 문을 만족한다. A[3] = 10 이다.

D[4] = max ( D[4] , D[3] + 1) == max ( 3 , 2 ) 이다.

따라서 D[4] = 3 그대로 유지된다.

if (30 > A[4]) 문을 만족하지 않는다.

D 배열을 전부 채운 결과

D 배열을 하나씩 채울 때 마다, 최대값을 cnt 변수에 기억한다.

최종 결과 4가 답으로 출력된다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int A[1001];
int D[1001];

int main(void){

     int len = 0, num = 0, cnt = 1;
    int i = 0, j = 0;

     scanf("%d", &len);

     for(i = 1; i <= len; i++){
         scanf("%d", &num);
         A[i] = num;
    } // 입력받기 끝 


    for(i = 1; i <= len; i++){

        D[i] = 1; // 자기자신 길이 1 로 초기화 

        for(j = 0; j <= i; j++){
            if(A[i] > A[j]){
                D[i] = max(D[i], D[j] + 1);
            }
        }
        cnt = max(cnt, D[i]);
    } 

     printf("%d", cnt);

    return 0;
}

문제

합분해 백준 2225번

리뷰

목표 합 n과 식의 개수 k를 관리하는 2차원 배열로 풀면 된다.

D[k] [n] 는 합이 n이 되는 k개의 항의 경우의 수를 저장한다.

D[2] [2] 는 합이 2가 되는 2개의 항의 경우의 수를 저장한다.

예를 들어, 0 + 2, 1 + 1, 2 + 0 이 있다. D[2] [2] = 3 이 저장된다.

목표합이 0 일 때, 항은 전부 0개 필요하다.

목표합이 1일 때, 항은 전부 그 숫자 1개가 필요하다. 따라서 아래와 같이 초기화 해준다.

     for(i = 0; i <= n; i++){   // 목표합이 i일 때, 항의 개수를 1개로 표현하면, 
        D[1][i] = 1; 
    }

2개의 항으로 3을 만드는 경우를 생각해보자.

k = 2, n = 3 이다.

0 + 3 -> 1개의 항으로 0이 되는 경우의 수 + 1개의 항으로 3이 되는 경우의 수

3+ 0 -> 1개의 항으로 3이 되는 경우의 수 + 1개의 항으로 0이 되는 경우의 수

2+ 1 -> 1개의 항으로 2이 되는 경우의 수 + 1개의 항으로 1이 되는 경우의 수

1+ 2 -> 1개의 항으로 1이 되는 경우의 수 + 1개의 항으로 2이 되는 경우의 수

이렇게 4가지 경우가 있으니까, D[2] [3] = 4 가 된다.

D[2] [3] = D[1] [0] + D[1] [1] + D[1] [2] + D[1] [3]

따라서 k=2 일 때, k-1 개의 항으로 0이 되는 경우의 수, 1이 되는 경우의 수, + ... n 이 되는 경우의 수를 더해야 한다.

D[k] [n] = D[k-1] [0] + D[k-1] [1] + ... + D[k-1] [n-1] + D[k-1] [n]

코드로 나타내면 3중 for문이 된다.

D[i] [j] 를 저장하기 전에 mod 연산이 필요하다는 것을 유의해야 한다.

    for(i = 2; i <= k; i++){ // 항의 개수 k  

        for(j = 0; j <= n; j++){  // 목표 합 n  

            for(s = 0; s <= j; s++){  // 0부터 목표 합까지 
                D[i][j] += D[i-1][s];
            }
            D[i][j] =  D[i][j] % MODNUM;
        }
    }

코드

#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

#define N_MAX 201
#define K_MAX 201
#define MODNUM 1000000000

// 2225  합분해  

long long D[N_MAX][K_MAX];  // MODNUM 으로 mod 연산 할꺼니까 long long형  

int main(void){

    int n, k = 0;
    int i, j, s = 0;

    scanf("%d %d", &n, &k); // 목표합, 항의 개수  

     for(i = 0; i <= n; i++){  // 목표합이 i 일 때, 1개 항으로 나타내는 경우의 수  
        D[1][i] = 1; 
    }

    for(i = 2; i <= k; i++){ // 항의 개수 k  

        for(j = 0; j <= n; j++){  // 목표 합 n  

            for(s = 0; s <= j; s++){ 

                D[i][j] += D[i-1][s];
            }

            D[i][j] =  D[i][j] % MODNUM;
        }
    }

    printf("%lld", D[k][n]); 

    return 0;
}

문제

제곱수의 합 백준 1699번

리뷰

배열 D[i] 는 i를 제곱수의 합으로 표현했을 때 최소항의 개수를 저장한다.

기본적으로 D[i] 는 1의 제곱으로 i 개 더하면 i를 만들수 있다. D[i] = i

ex) D[1] = 1개, D[2] = 2개 ( 1^2 + 1^2 )

i를 제곱수로 표현할 때, 자신보다 작은 수의 제곱수들로만 구성되어 있다.

아래는 D[i] 의 최소항 개수를 1부터 5까지 구해본 것이다.

D[1] = 1개 ( 1^2)

D[2] = 1개 ( 2^2)

D[3] = 2개 ( 1^2 + 2^2)

D[4] =1개 ( 2^2 )

D[5] = 2개 ( 2^2 + 1^2 )

점화식은 다음과 같다.

for(i = 1; i <= n; i++){

    D[i] = i; // i를 1의 제곱의 합으로만 나타내면 항의 개수 i개  

    for(j = 1; j*j <= i; j++){  // i보다 작은 제곱수들 

        D[i] = min(D[i], D[i- j*j] + 1);

    }
}

n = 5로 주어질 때, D[5] 를 구해보자.

기본적으로 D[5] 는 1의 제곱의 합으로만 나타내서 5개의 항으로 구성할 수 있다. D[5] = 5개

5 보다 작은 제곱수는 1과 2가 있다.

그래서 i보다 작은 제곱수들(1 , 2 )의 합으로 i를 표현할 수 있다.

그래서 D[5] 는 D[2] 값에 1을 더한 경우, D[1의 제곱] 값에 1을 더한 경우 로도 나타낼 수 있다.

D[5] = D[2] + 1

D[5] = D[1] + 1

이 중에서 가장 작은 값이 D[5] 에 들어가야 한다.

D[5] = min ( 5, D[2] + 1, D[1] + 1 )

코드

#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

// 1699번 제곱수의 합  

int D[100001]; 

int main(void){

     int n = 0 ;      
    int i, j = 0;

    scanf("%d", &n);

    for(i = 1; i <= n; i++){

        D[i] = i; // i를 1의 제곱의 합으로만 나타내면 항의 개수 i개  

        for(j = 1; j*j <= i; j++){  // i보다 작은 제곱수들 

            D[i] = min(D[i], D[i- j*j] + 1);

        }
    }

     printf("%d", D[n]);

    return 0;
} 

콜라츠 추측 

프로그래머스 level 1 문제 

리뷰 

문제에 테스트 케이스 3개가 나와있는데, 626331 이 제대로 답이 안나왔었다. 

이상해서 계산과정 while 문 내부를 출력해보니까,

홀수 가 된 경우에 * 3 하는 과정에서 int 표현 범위를 넘어가서 음수로 표현되고 난리가 났었다. 

long long 으로 변환하고 나서 실행해보니 626331 의 답이 -1로 잘 나왔다.

근데, 답을 제출했더니 테스트 케이스 1개가 틀렸다. 이유는 1때문이었다. 

solution 함수에 입력이 1로 들어왔을 때는, 연산할 필요가 아예 없으니 처음부터 예외처리가 필요하다고 했다. 

코드 

#include <string>
#include <vector>

using namespace std;

int solution(int num) {
    
	int answer = 0;
    int limit = 500;
    long long temp = num; // 자료형 변환 
    
    if(num == 1) return 0; // 1은 연산 필요 없다
    
    while(limit--){
      
      if(temp % 2 == 0){
        temp /= 2;

      }else{
      	temp = (temp * 3) + 1;
      }

      answer++;
      limit--;

      if(temp == 1) break;
	}

    return temp != 1 ? -1 : answer;

}

문제

스티커 백준 9465번

리뷰

문제에 나와있는 그림 b 에서는

50, 50, 100, 60을 떼가야 260 최대 점수라는 예시 덕분에 풀 수 있었다.

지그재그로 떼는 경우 뿐만 아니라,

자기와 다른 행의 옆옆 스티커를 뗐을 때 최대값을 발견할 수도 있다는 것이다.

배열 S는 주어진 스티커 점수 배열이다.

배열 D를 D [행] [열] 이라고 하고, 해당 행과 열을 마지막으로 뗐을 때의 최대 스티커 점수를 저장한다.

하나의 열 마다 순회하는 for문을 만들고,

그 안에서 1행의 마지막일 경우의 최대값, 2행이 마지막일 경우의 최대값을 점화식으로 계산해서 D에 저장한다.

    //  D [행] [열]  
    D[1][i] = S[1][i] + max(D[2][i-1], D[2][i-2]);
    D[2][i] = S[2][i] + max(D[1][i-1], D[1][i-2]);

예를 들면,

D[1] [3] = 자기자신 S[2] [3] + max( D[2] [1] , D [2] [2] )

대각선으로 더했을 때 최대인지, 반대편 행의 옆옆 칸을 더했을 때 최대인지를 비교하면 된다.

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

// 스티커 (BOJ 9465)

int S[3][100001]; // 입력받은 스티커 점수  
int D[3][100001];
int n, max_sum;

int Sticker(){

    // 1열 
    D[1][1] = S[1][1];
    D[2][1] = S[2][1];

    // 2열  
    D[1][2] = D[2][1] + S[1][2];
    D[2][2] = D[1][1] + S[2][2];

    for(int i = 3; i <= n; i++){

        D[1][i] = S[1][i] + max(D[2][i-1], D[2][i-2]);
        D[2][i] = S[2][i] + max(D[1][i-1], D[1][i-2]);
    }

    return max(D[1][n] , D[2][n]);
}

int main(void){

    int T = 0;
    int i = 0, num = 0;

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        for(i = 1; i <= n; i++){
            scanf("%d", &num);
            S[1][i] = num;
        }

        for(i = 1; i <= n; i++){
            scanf("%d", &num);
            S[2][i] = num;
        }

        printf("%d\n", Sticker());

    }

    return 0;
}

문제

계단 오르기 백준 2579번

리뷰

점화식을 구하는 데 조금 헤맸다.

계단이 1, 2, 3, 4번이 있고, 만약 현재 4번째 계단에 위치한다면,

max(2번째 계단까지의 최대값 + 4번째 계단점수 , 3번째 계단까지의 최대값 + 4번째 계단점수)

이렇게 비교해서 4번째 계단까지의 최대값을 구할 수 있을 줄 알았는데, 틀렸다.

이유는 4번이 마지막 계단(반드시 밟아야 하는 계단) 이라면,

2번을 밟고 4번을 밟았는지, 1번, 3번을 밟고 4번을 밟았는지를 비교해야 했다.

(OXOO or OOXO )

3번을 밟은 경우에는, 반드시 1번을 밟고 온 경우만 고려해야 한다. (왜냐하면 1, 2, 3 연속으로 밟으면 안되기 때문이다. )

case1) 1번 계단까지의 최대값 + 3번 계단점수 + 4번 계단점수

case2) 2번 계단까지의 최대값 + 4번 계단점수

이 두 가지의 경우를 비교하면서 DP로 푼다.

// i : 도착 계단 (반드시 밟아야함)

    case1 = D[i-3] + S[i-1] + S[i]; 
    case2 = D[i-2] + S[i];

코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int S[301]; // i번 계단의 점수 
int D[301]; // i번 계단까지의 최대점수 기록 

int Max(int stair_size){

    int i = 0;
    int case1, case2 = 0;

    for(i=3; i<= stair_size; i++){

        case1 = D[i-3] + S[i-1] + S[i];
        case2 = D[i-2] + S[i];

        D[i] = max(case1, case2);

    }

    return D[stair_size];
}

int main(void){

    freopen("input.txt", "rt", stdin);

    int stair_size, i = 0, num = 0;

    scanf("%d", &stair_size);

    for(i = 1; i <= stair_size; i++){
        scanf("%d", &num);
        S[i] = num; // 계단의 점수 입력받음 
    }

    D[1] = S[1];
    D[2] = D[1] + S[2];

    printf("%d", Max(stair_size));

    return 0;
}

문제

1,2,3 더하기5 백준 15990번

리뷰

n을 1,2,3의 합으로 나타내는 경우의 수를 구해봤을 때, 규칙이 있는지 정수 8까지 경우를 써봤다.

정수 n이 3의 배수인 경우에는 이전 합에서 * 2를 하면 되는줄 알았는데, 점화식이 틀렸다.

다른 분 풀이를 보니까 n을 때, 마지막 수가 i인 경우를 따져봤다. (i는 1, 2, 3 )

연속으로 같은 숫자를 쓸 수 없음을 이용한 것이다.

정수 n 이 주어지면, 마지막 수가 i인 경우 (i는 1, 2, 3 ) D[n] [1] , D[n] [2] , D[n] [3] 으로 식을 세우는 것이다.

왜냐하면 1+1+1 처럼, 연속된 수는 못오기 때문이다.

1 앞에는 2, 3만 올 수 있다.

2 앞에는 1, 3만 올 수 있다.

3 앞에는 1, 2만 올 수 있다.

n = 6인 경우를 보자.

D[6] [1] 을 구하기 위해서는 6에서 1을 뺀 D[5] 라인을 살펴봐야 한다.

왜냐하면 1 앞에는 2와 3이 올 수 있으므로, n에서 1을 뺀 5의 경우의 수를 봐야 한다.

2가 마지막에 오는 경우의 수 D[5] [2] 와 + 3이 마지막에 오는 경우의 수 D[5] [3] 를 더하면 D[6] [1] 이 된다.

2가 마지막에 오는 경우의 표현들 D[5] [2] 뒤에 +1 을 해주면 6이 된다.

3이 마지막에 오는 경우의 표현들 D[5] [3] 뒤에 + 1 해주면 6이 된다.

마찬가지로 D[6] [2] 를 구하기 위해서는 6에서 2를 뺀 D[4] 라인을 살펴봐야 한다.

왜냐하면 2 앞에는 1과 3이 올 수 있는데, 4에서 1과 3으로 끝난 경우의 수들을 봐야 하기 때문이다.

그래서 1이 마지막에 오는 경우의 수 D[4] [1] 과 3이 마지막에 오는 경우의 수 D[4] [3] 를 더하면 D[6] [2] 이 된다.

점화식은 아래와 같다.

D[n] [1] = D[n-1] [2] + D[n-1] [3]

D[n] [2] = D[n-2] [1] + D[n-2] [3]

D[n] [3] = D[n-3] [1] + D[n-3] [2]

코드

#include <stdio.h>
#define MODNUM 1000000009
using namespace std;


long long D[100001][4]; 

long long sum_case(int num){

    int i = 0;

    for(i=4; i <= num; i++){
        D[i][1] = (D[i-1] [2] + D[i-1] [3]) % MODNUM;
        D[i][2] = (D[i-2] [1] + D[i-2] [3]) % MODNUM;
        D[i][3] = (D[i-3] [1] + D[i-3] [2]) % MODNUM;
    }

    return (D[num][1] + D[num][2] + D[num][3])  % MODNUM;

}

int main(void){

    freopen("input.txt", "rt", stdin);

    int test_case, n = 0, num = 0;

    D[1][1] = D[2][2] = 1;

    D[3][1] = 1;
    D[3][2] = 1;
    D[3][3] = 1;

    scanf("%d", &test_case);

    while(test_case--){
        scanf("%d", &num);
        printf("%lld\n", sum_case(num));
    }

    return 0;
}

마지막으로 mod 연산 때문에 틀려서 참고한 코드가 있다.

sum_case() 의 반환값도 long long, D배열의 반환값도 long long으로 해야 맞출 수 있었다.