글 읽기 - c++ 9095번 1로만들기 문제

justking 6년 전 0

13번째줄에 d[0] = 1이게이해가안됩니다.

dp를 많이풀면 감각이생긴다 이러시는데 그감각 설명좀 해주세요ㅠ

#include <cstdio>
#include <iostream>

using namespace std;


int main(){
    int t;
    scanf("%d", &t);

    while( t-- ){
        int d[15] = {};
        d[0] = 1;
        int k;
        scanf("%d", &k);
        
        for(int i = 1; i <= k; i++){
        	
            if( i-1 >= 0){
                d[i] += d[i-1];
            }
            if( i-2 >= 0){
                d[i] += d[i-2];
            }
            if( i-3 >= 0 ){
                d[i] += d[i-3];
            }
        }
        printf("%d\n", d[k]);
    }
    return 0;
}

kgj291 6년 전 0

저도 초보긴 한데

다른분들은 어떻게 하는지 잘 모르지만

저같은 경우는 그 다음값인

d[1]=? 에 맞춰서 d[0] 값을 넣어요

다이나믹프로그래밍이 무한루프 돌아가지 않기위해 초기값 하나쓰는데

d[1]=1이건 직관적으로 바로 알수있으니

d[1]=1이 나오기 위해서는 내가 만든 식에 d[0]=1의 초기값을 넣어주면 되는구나

이렇게 생각하고 d[0]값을 넣어요

djm03178 6년 전 0

일단 1로 만들기 문제는 아니군요.

dp[0] = 1이라는 건 1, 2, 3을 하나도 사용하지 않고 그대로 둔 한 가지 경우가 0을 만드는 유일한 방법이기 때문에, 그 지점에 1을 넣고 시작할 수 있는 것입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 9095번 1로만들기 문제

justking 6년 전 0

kgj291 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말