[BOJ] μƒˆλΌμΉ˜κΈ°(17291)

[λ°±μ€€(BOJ)] μƒˆλΌμΉ˜κΈ°(17291) C++

문제 : BOJ_17291번 μƒˆλΌμΉ˜κΈ°

문제 μ„€λͺ…

μœ„μƒμ •λ ¬, DP(λ‹€μ΄λ‚˜λ―Ή ν”„λ‘œκ·Έλž˜λ°)

1년에 ν•œ λ§ˆλ¦¬μ˜€λ˜ λ²Œλ ˆκ°€ 맀년 λΆ„μ—΄ν•˜κ³ 
1)ν™€μˆ˜ 연도에 λΆ„μ—΄ν–ˆλ˜ λ²Œλ ˆλŠ” 3번 λΆ„μ—΄ μ‹œ 사망
2)짝수 연도에 λΆ„μ—΄ν–ˆλ˜ λ²Œλ ˆλŠ” 4번 λΆ„μ—΄μ‹œ 사망
μž„μœΌλ‘œ, ν•΄λ‹Ή 년도에 μ‚΄μ•„μžˆλŠ” λ²Œλ ˆλ“€μ΄ μ–Έμ œ λΆ„μ—΄ν–ˆλŠ”μ§€λ₯Ό μ €μž₯ν•΄μ•Ό 됨으둜 2쀑 dpλ₯Ό 톡해 ν’€ 수 μžˆμŠ΅λ‹ˆλ‹€.


Solution

이쀑 배열을
dp[ν˜„μž¬ 연도][νƒœμ–΄λ‚œ 연도] = 벌레 수
둜 μ •ν•΄μ„œ ν’€μ–΄λ΄…μ‹œλ‹€. 2쀑 포문을 톡해 λ§€λ…„λ§ˆλ‹€
dp[ν˜„μž¬ 연도][ν˜„μž¬ 연도] = dp[ν˜„μž¬ 연도-1][νƒœμ–΄λ‚œ 연도]
둜 λΆ„μ—΄λœ 벌레λ₯Ό μ €μž₯ν•΄μ€€λ‹€.
기쑴에 λ‚¨μ•„μžˆλ˜ λ²Œλ ˆλŠ” ν™€μˆ˜ 3λ…„, 짝수 4λ…„ μ•ˆμ— λΆ„μ—΄λœ 벌레라면
dp[ν˜„μž¬ 연도][λΆ„μ—΄λœ 연도] = dp[ν˜„μž¬ 연도-1][νƒœμ–΄λ‚œ 연도]
둜 μ €μž₯ν•΄μ€λ‹ˆλ‹€.


Description

기쑴에 λ‚¨μ•„μžˆλŠ” 벌레λ₯Ό μƒˆλ‘œμš΄ 연도에 μ €μž₯ν•  λ•Œ 쑰건문을 μ£Όμ˜ν•΄μ„œ μ§œλ„λ‘ ν•΄μ•Ό ν•©λ‹ˆλ‹€.

#include <iostream>
using namespace std;
int dp[21][21]; // dp[ν˜„μž¬ 연도][νƒœμ–΄λ‚œ 연도] = 벌레 수
int main(void) {
	dp[1][1] = 1;
	for (int i = 2; i <= 20; i++) {
		for (int j = 1; j < i; j++) {
			if (j % 2) { // ν™€μˆ˜ 연도에 νƒœμ–΄λ‚œ 벌레
				if (i - j < 3) dp[i][j] += dp[i - 1][j];
			}
			else if (i - j < 4) dp[i][j] += dp[i - 1][j]; // 짝수 연도에 νƒœμ–΄λ‚œ 벌레
			dp[i][i] += dp[i - 1][j]; // ν˜„μž¬ 연도에 νƒœμ–΄λ‚œ 벌레
		}
	}
	int year;
	scanf("%d", &year);
	int result = 0;
	for (int i = 1; i <= year; i++) result += dp[year][i];
	printf("%d\n", result);
}