BOJ

다음순열 >10972 다음순열 코드 > 풀이방법

문제 > 코드 > 풀이 > ## d[n]을 n이 1,2,3의 합으로 표현되는 개수로 두었다 예를들어 x + x ... + x + O = n 인겨우 O에 자리에 1,2,3이 올수 있으므로 [x+x...+x] = n - O

문제 > 코드 > 풀이 > ### n개의 번호에서 6개를 중복없이 선택해야하기 때문에 새로운 vector를 만들어 n-6개의 0과 6개의 1을 넣어줌, 새로운 vector를 순열(next_permutation)를 이용

2\*n 타일링 문제에서 마지막에 2\*2 도형이 추가되므로 i-2번째를 더해주면 됌

문제 > 코드 > 풀이 > ## 숫자 n을 1로 만드는 방법은 n-1 + 1 or n/2 + 1 or n/3 + 1 을 1로 만드는 것과 동일한것을 이용해줌, 다이나믹프로그래밍을 이용해 d[i]에 값을 저장하여 풀어주었다

문제 > 코드 > 풀이 > ## i번째는 i-1 과 i-2의 합이라는 점화식을 사용해 문제를 품

dn n은 숫자의길이, l은 마지막에 있는 숫자로 만약 l이 0과 9가 아닐때 각각 dn-1,dn-1 을 더해주는 점화식으로 세워 풀었다.

di = i자리 수와 L로 끝나는 이친수의 개수 L은 0,1 만 올수있으므로 di 에 di-1 와 di-11 를 더해줌 0 앞에는 0과 1이 올수 있기 때문 di 에 di 을 더해줌 1앞에는 0만 올수있기 때문에

각 숫자마다 순열의 길이를 di 저장해주고, di는 그 i번째 숫자가 앞에숫자보다 크고, 순열의 길이가 가장긴 값에 +1 을 해서 더해주었다

https://www.acmicpc.net/problem/1912i번째 수와 i-1번째 수의 합이 i번째 보다 크다면 di에 저장하는것을 이용