C C++/C C++ 백준69 C언어 백준 9465번 스티커 문제 풀이 이번 DP 문제는 각 셀의 값, 스티커 누적 점수를 배열에 담아 누적하는 구조로 문제를 풀이할 수 있다. 기본 구조 현재 스티커 점수인 배열 arr을 선언하고, 스티커 누적 점수인 배열 dp를 선언하여 사용한다. 위와 같이 arr과 dp 기본 구조를 만들 수 있다. 스티커 선택 (점화식 세우기) 이제 어떤 방식으로 스티커를 선택해야 최대 누적 값을 얻을 수 있을까? 바로 'N'번 째 선택을 할 때 N-1번 째 스티커와의 관계를 생각하면 된다. 맨 오른쪽인 N번 째로 생각 해 보면, 아래 1번과 2번 패턴 밖에 없다. 스티커 누적 점수는 이전 스티커 최댓값에 현재 선택하는 스티커 최댓값을 더하는 구조이다. 따라서 선택 셀[1]은 고려할 필요는 없고, 선택 셀[2]의 누적 점수에 선택 셀[3]을 .. 2022. 6. 10. C언어 백준 2193번 이친수 문제 풀이 이친수를 나열 해 보면 피보나치 수열과 동일한 패턴을 보이고 있기 때문에 피보나치 수열을 사용하여 문제를 풀이한다. 코드 #include int n; long long arr[100]={0,}; int sum; int main(void) { scanf("%d", &n); arr[0]=0; arr[1]=1; arr[2]=1; for(int i=3; i 2022. 6. 10. C언어 백준 11057번 오르막 수 문제 풀이 오르막 수는 수의 자리가 자릿수가 증가할 때 오르는 수이다. 규칙을 파악하여 점화식을 세워야하는 문제이다. 우선 DP 배열을 어떻게 구성할 지 생각 해 보자. DP[자릿수][숫자] = 개수 로 세울 수 있다. 몇 번째 자릿수인지, 해당 자릿수의 오는 숫자 0~9, 그리고 배열 안에 담긴 경우의 수가 몇 개인지이다. 아래 표에서 N-1번째와 N번째 자리만 보더라도 알 수 있다. N번째 자리에 올 수 있는 수는 N-1번째 자릿수보다 같거나 크면 가능하다. 따라서, 0이었다면 0~9가 올 수 있는 것이고, 이 경우의 수는 N-1번째 자릿수의 0~9에 해당하는 경우의 수를 모두 더하면 전체 값이 나온다. 즉, DP[N][0]=DP[N-1][0]+DP[N-1][1]+.....+DP[N-1][9]인 것을.. 2022. 6. 10. C언어 백준 10844번 쉬운 계단 수 문제 풀이 계단 수는 자리 차이마다 1의 차이를 가지고 있는 수이다. DP에서 중요한 점은 배열로 풀 때 - DP의 인덱스는 어떤 값을 넣을 것이고 - 그 배열 안에는 어떤 값이 들어갈 지 - 점화식을 어떻게 세울 것인지 인 것 같다. 이번 문제도 마찬가지로 인덱스 값을 어떤 값을 넣지와 배열 안의 값이 어떤 값이 들어갈 지가 중요하였다. DP[몇 번째 수][자릿수] = 총 개수 로 정의할 수 있다. 이 때, 바로 옆 숫자 대비 1씩 다르다. 왼쪽부터 n번째 자릿수는 n-1번째 자릿수 값+1과 n-1번째 자릿수 값-1의 개수에서 오기 때문에 둘을 더하면 된다. 예를 들어 3번째 자릿수 3인 경우, 2번째 숫자 2의 개수와 2번째 숫자 4의 개수를 더한 개수가 된다. 다만, 0과 9는 올 수 있는 경우가 .. 2022. 6. 9. 이전 1 2 3 4 5 6 7 8 ··· 18 다음