다이나믹 프로그래밍3 10844 쉬운 계단 수 (자바스크립트) 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.====문제 분석자릿수를 row로 두고 각 자릿수를 만들 때 마지막 숫자로 올 수 있는 0~9를 col로 둔 뒤 각 자릿수의 숫자 조합을 만들 때 마지막으로 오는 숫자의 횟수를 dp[row][col]에 기록해두는 문제이다.만약 세 자리수를 만든다면 이는 두 자리수 중 마지막에 1을 쓴 경우의 수에 0 또는 2를 추가하면 된다.이를 점화식.. 2025. 1. 8. [백준] 12969 ABC 문제 정수 N과 K가 주어졌을 때, 다음 두 조건을 만족하는 문자열 S를 찾는 프로그램을 작성하시오. 문자열 S의 길이는 N이고, 'A', 'B', 'C'로 이루어져 있다. 문자열 S에는 0 ≤ i < j < N 이면서 S[i] < S[j]를 만족하는 (i, j) 쌍이 K개가 있다. 입력 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 30, 0 ≤ K ≤ N(N-1)/2) 출력 첫째 줄에 문제의 조건을 만족하는 문자열 S를 출력한다. 가능한 S가 여러 가지라면, 아무거나 출력한다. 만약, 그러한 S가 존재하지 않는 경우에는 -1을 출력한다. == 솔루선 문자열에 A를 추가하면 s[i] 2023. 12. 18. [dp] 11333 4xn 타일링 (파이썬) 문제 icpc 왕국에는 아주 못된 왕 유빈이가 있었다. 유빈이에게는 4×n 크키의 카펫이 하나 있었다. 유빈이는 신하들에게 이 카펫을 3×1 타일과 1×3 타일로 빈틈없이 메우라는 명령을 내렸다. 여러분이 신하들을 도와서 4×n 크기의 카펫을 3×1 타일과 1×3 타일로 메우는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 테스트 케이스의 수 T가 주어진다. (1 2023. 9. 16. 이전 1 다음
