코테 DP (2) 썸네일형 리스트형 백준 9465 번 - 스티커 (C++/DP/Dynamic Programming) 문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 접근법 전형적인 DP문제 라지만 내가 지금까지 풀어왔던거와 살짝 달라서 매우 헤매다, 검색해서 힌트를 얻고 풀었다. 스티커의 값을 구하는데 규칙이 없어보이지만, 스티커는 1칸 대각선, 2칸 대각선으로만 이동할 수 있다. (양 옆이 인접한 곳으로는 이동하지 못하므로). 3칸 대각선 (1칸 대각선을 3번 이동한게 무조건 더 크다) 부터는 다른 값을 거쳐갈 수 있어서 불가능 하다. 이를.. 백준 10844 번 - 쉬운계단수 (C++/DP/동적계획법/Dynamic Programming) 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 접근법 동적계획법으로 접근해야 하는 문제이다. 여러가지 예시를 보며 문제부터 파악했다. 자리수를 Y, 맨 뒤 index에 따른 개수를 X로 두고, 2차원 배열을 만들면 cnt[101][10]; 정도로 크기를 두며 이전 값을 참고해 채워나가면 될거같다. 자리수는 2인 것 끝자리 0 -> 10 끝자리 1-> 21 끝자리 2->32,12 끝자리 3->23,43 끝자리 4->34,54 . . . 끝자리 8->78,98 끝자리 9->89 맨 앞자리는 0이 올수 없으므로 위 17가지가 계단수이다. 자리.. 이전 1 다음
