PS/BOJ
BOJ 9461 파도반 수열
boj 9461 파도반 수열 - 문제 링크 https://www.acmicpc.net/problem/9461 - 문제 해설 첫 5항만 제외하고 나머지 항들은 전부 규칙을 따라 증가하는 형태이다. P(1)부터 P(10)을 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다. 길이가 3인 삼각형은 1과 2를 더해서 생기고, 길이가 4인 삼각형은 1과 3을 더해서, 길이가 5인 삼각형은 1과 4를 더해서 생긴다. D[i] = D[i-1] + D[i-5] 의 규칙을 따라 증가한다. 그러므로 1~5항을 따로 초기화해주고 나머지는 위 점화식을 따라 구해준다. - 코드 보기 #include using namespace std; int t; int n; long long P[105]; int main(voi..
BOJ 2133 타일 채우기
boj 2133 타일 채우기 n이 홀수일 때, 타일을 전부 채울 수 있는 방법은 없다. 그러므로 n이 짝수일 때만 살펴보면 된다. 테이블 D[i]를 n이 i일 때, 타일을 전부 채울 수 있는 방법 수라고 정의하자. 타일이 2칸일 때 채울 수 있는 방법의 수가 3가지인 것은 쉽게 알 수 있다. 그리고 힌트를 보면 4칸의 경우 2칸인 경우를 이용하지 않고 채우는 방법이 2가지가 있다는 것을 알 수 있다. 이 사실만으로 간단하게 점화식을 D[i] = D[i-2]x3 + D[i-4]x2 라고 하면 틀린다. 위의 사진을 보면, 타일이 2칸씩 늘어날 때마다 채우는 방식 2가지가 추가된다. 이를 바탕으로 점화식을 구현해보자. D[i] = D[i-2]x3 + D[i-4]x2 + D[i-6]x2 + ... + D[0]x..
BOJ 1699 제곱수의 합
boj 1699 제곱수의 합 수가 주어지면 그 수를 제곱수들의 합으로 표현할 때, 최소의 항 갯수를 구하는 문제이다. 모든 수는 1의 합으로 표현할 수 있기에 최대의 항 갯수는 입력된 수의 크기와 동일하다. 그러므로, 테이블 D[i]를 i를 제곱수의 합으로 표현할 때의 최소의 항 갯수라고 정의하면, D[i] = i 라고 초기 값을 지정해줄 수 있다. 최소의 항 갯수를 구하는 방법은 간단하다. i에서 i를 넘지 않는 제곱수를 빼면서 최소 항의 갯수를 변경해주는 것이다. 이를 점화식으로 나타내보자. D[i] = min(D[i], D[i - 제곱수]+1) 이때, +1을 해주는 이유는 제곱수에 해당하는 항 갯수를 더해주는 것이다. #include #include using namespace std; int n;..
BOJ 2579 계단 오르기
boj 2579 계단 오르기 문제의 조건에 따라 마지막 계단은 무조건 밟아야한다. 계단은 연속으로 두번까지 밟을 수 있다. 마지막 계단을 밟는데, 그 마지막 계단이 연속으로 밟은 첫번째 계단이냐 두번째 계단이냐로 경우의 수를 나눌 수 있다. 이를 바탕으로 테이블을 정의해보자. D[i][1] = 마지막 계단이 i번째 계단이고 1개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값 D[i][2] = 마지막 계단이 i번재 계단이고 2개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값 D[i][1]의 경우는 i-1번째 계단을 밟지 않으므로, 마지막 계단이 i-2번째 계단일 경우의 계단 점수의 최댓값에서 i번째 계단 점수를 더하면 된다. D[i][2]의 경우는 i-1번째 계단을 무조건 밟고, i-2번째 ..
BOJ 1912 연속합
boj 1912 연속합 간단한 DP 문제이다. a[i]는 수열이 담긴 배열이고, 테이블로 D[i]는 i번째 원소를 마지막으로 하는 연속된 수열 합의 최댓값이라고 정의한다. 합이므로 초기 값은 원소 자기 자신의 값이다. 그러므로 D[i] = a[i]로 초기화한다. 수열이 연속된다는 것을 인지하면 D[i] = max(D[i], D[i-1] + a[i]) 이라는 점화식이 쉽게 만들어진다. 각 수는 -1000에서 1000 사이이 수 이므로 ans는 초기 값으로 -1001을 주었다. 위 내용을 바탕으로 코드를 구현해보자. #include #include using namespace std; int n; int a[100005]; int D[100005]; int ans = -1001; int main(void) ..