https://www.acmicpc.net/problem/1947
완전 순열의 개념을 알아야함
완전 순열 : n명의 사람이 자신의 모자를 벗어두었다가,
다시 쓰는데 모든 사람이 자기의 것이 아닌 모자를 쓰는 경우의 수
d[i]
i 명이 선물을 나누는 경우의 수
a1 a2 a4 a4 …. aj … ai
aj가 i 선물을, ai가 j 선물을 가지는 경우
나머지 i-2 명이 선물을 나눠 가지면 된다 => d[i-2]
그리고 aj는 ai를 제외한 명 수중 한 명 이므로 i-1
aj가 i 선물을 가지고, ai가 j 선물으 가지지 않는 경우
aj를 제외한 나머지 i-1명이 선물을 나눠 가지면 된다. => d[i-1]
그리고 aj는 ai를 제외한 명 수중 한 명 이므로 i-1
그런데, 계속해서 런타임 에러가 발생했음
d[2]를 초기화할 때, 반복문 안에서 조건을 걸어서 하지 않고,
반복문 안에서 초기화
https://www.acmicpc.net/problem/2306
풀어본 DP 문제 중 제일 어려움
d[i, j]
a[i..j] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이
d[i, j] = 2
d[i, j] = d[i+1, j-1] + 2
d[i, j] = d[i, k] + d[k+1, j]
- a[i...k] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이 => d[i, k]
- a[k+1...j] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이 => d[i, k]
https://www.acmicpc.net/problem/1015
어려웠음
i 번째 값과
j 번쨰 (0번째 ~ i-1번째) 값을 비교하여
큰 값의 index (i or j) 에 해당하는 위치의 배열 값을 ++
쉽게 생각해서,
a배열의 값들이 동일선상에 위치하는데,
비내림차순으로 정렬하기 위해 몇 번씩 뒤로 이동시켜야 하는지 카운트
ex)
B[p[0]] = A[0] = 7 <-
B[p[1]] = A[1] = 4 <-
B[p[2]] = A[2] = 2 <-
B[p[3]] = A[3] = 3 <- 기준
B[p[4]] = A[4] = 9
B[p[5]] = A[5] = 10
3을 기준으로 7, 4, 2 와 비교
3과 7 => 7이 더 크다 => 7은 한 번뒤로 가야함 => B의 index 값 증가
3과 4 => 4가 더 큼 => 4는 한 번뒤로 가야함 => B의 index 값 증가
3과 2 => 3이 더 큼 => 3은 한 번뒤로 가야함 => B의 index 값 증가
https://www.acmicpc.net/problem/2968
어렵다
d[i][j][m]
길이가 i인 수열,
인접 비트 개수가 j,
마지막 비트가 m인 ( m : 0 or 1 )
수열의 경우의 수
마지막 비트가 0
마지막 비트가 1
https://www.acmicpc.net/problem/2631
https://www.acmicpc.net/problem/1075
n의 최고자리수를 제외하고 다 0으로 만들기
ex) n이 2031이면 => 2000으로
f로 나누어 떨어지는지 확인. 나누어 안 떨어지면 +1
끝 두자리 출력
계속 틀렸다고 뜸..
https://www.acmicpc.net/problem/1309
동물 수에 따라 식을 세우려고 함
d[1] : 동물 한 마리 들어갔을 때 경우의 수
d[2] : 동물 두 마리 들어갔을 때 경우의 수
…
이런식으로 하면 d[n-1] 과 d[n] 을 연결시키기가 어려움
n-1 번째 줄 까지 우리에 맞게 들어갔다고 보고
n 번째 줄에 어떻게 올 수 있는지 고려해야함