[BOJ] ์˜ค๋ฅด๋ง‰ ์ˆ˜(11057)

[๋ฐฑ์ค€(BOJ)] ์˜ค๋ฅด๋ง‰ ์ˆ˜(11057) C++

๋ฌธ์ œ : BOJ_11057๋ฒˆ ์˜ค๋ฅด๋ง‰ ์ˆ˜

๋ฌธ์ œ ์„ค๋ช…

DP

DP๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์˜ค๋ฅด๋ง‰ ์ˆ˜์ž…๋‹ˆ๋‹ค.
1๋ถ€ํ„ฐ 1,000์˜ ์ˆ˜ ์ค‘ ํ•˜๋‚˜์ธ N์ด ์ฃผ์–ด์ง€๋ฉด, N ์ž๋ฆฌ๋กœ ์ด๋ฃจ์–ด์ง„ ์˜ค๋ฅด๋ง‰ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
์—ฌ๊ธฐ์„œ ์˜ค๋ฅด๋ง‰ ์ˆ˜๋ž€, ๊ฐ€์žฅ ํฐ ์ž๋ฆฟ์ˆ˜๋ถ€ํ„ฐ ๊ฐ€์žฅ ์ž‘์€ ์ž๋ฆฟ์ˆ˜๊ฐ€ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์˜ฌ๋ผ๊ฐ€์•ผ ํ•˜๋Š”๋ฐ, ์ด ๋ฌธ์ œ์—์„  ์ˆ˜๊ฐ€ ๊ฐ™์•„๋„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ธ์ •ํ•ด ์ค๋‹ˆ๋‹ค.
๋˜ ํŠน์ดํ•œ ์ ์€ ์ˆ˜๊ฐ€ 0์œผ๋กœ ์‹œ์ž‘ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Solution

์ €๋Š” 2์ฐจ์› dp ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ–ˆ์Šต๋‹ˆ๋‹ค.

dp[์ˆ˜์˜ ๊ธธ์ด][๊ฐ€์žฅ ํฐ ์ž๋ฆฟ์ˆ˜์˜ ์ˆ˜] -> ๋งŒ์กฑํ•˜๋Š” ์ˆ˜์˜ ์˜ค๋ฅด๋ง‰ ์ˆ˜์˜ ๊ฐœ์ˆ˜

์šฐ์„  N์ด 1์ธ ๊ฒฝ์šฐ๋ฅผ ์ƒ๊ฐํ•ด๋ด…์‹œ๋‹ค.
๋ฌธ์ œ์˜ ์กฐ๊ฑด์ด '์ˆ˜๋Š” 0์œผ๋กœ ์‹œ์ž‘ํ•  ์ˆ˜ ์žˆ๋‹ค.' ์ž„์œผ๋กœ, 0,1,2,3 โ€ฆ 7,8,9 => 10๊ฐœ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.
์•ž์„  2์ฐจ์› ๋ฐฐ์—ด์˜ ์กฐ๊ฑด์— ๋งž์ถ”๋ฉด dp[1][0]=1 , dp[1][1]=1 , โ€ฆ dp[1][9]=1 ์ด ํ• ๋‹น๋ฉ๋‹ˆ๋‹ค.
์ด๋ ‡๊ฒŒ ํ•œ ์ž๋ฆฟ์ˆ˜์˜ ์˜ค๋ฅด๋ง‰ ์ˆ˜์— ๋ชจ๋‘ 1์„ ํ• ๋‹นํ•ด ์ฃผ๊ณ , ์ž๋ฆฟ์ˆ˜๊ฐ€ ์˜ฌ๋ผ๊ฐ„๋‹ค๋ฉด ๊ตฌํ•˜๊ณ ์ž ํ•˜๋Š” ์ˆ˜์˜ ๊ธธ์ด -1์˜ dp๋ฅผ ๋ด์ฃผ๊ณ  ๋” ํ•ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.
์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆ˜์˜ ๊ธธ์ด๊ฐ€ 3์ด๊ณ  ๊ฐ€์žฅ ํฐ ์ž๋ฆฌ์ˆ˜๊ฐ€ 5์ธ ์˜ค๋ฅด๋ง‰ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.
๊ทธ๋ ‡๋‹ค๋ฉด, ์ธ์ ‘ํ•œ ์ˆ˜๊ฐ€ ๊ฐ™์•„๋„ ์˜ค๋ฆ„์ฐจ์ˆœ์ด๊ธฐ ๋•Œ๋ฌธ์—,

dp[3][5] = dp[3-1][5] + dp[3-1][6] + dp[3-1][7] + dp[3-1][8] + dp[3-1][9];

์ด๋ผ๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
for ๋ฌธ์„ ์‚ฌ์šฉํ•ด ๋ฐ”ํ…€์—… ๋ฐฉ์‹์œผ๋กœ ๊ฐ ์˜ค๋ฅด๋ง‰ ์ˆ˜๋ฅผ ํ• ๋‹นํ•ด ์ฃผ๋ฉด ๋‹ต์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Description

  • vector๋ฅผ ์ด์šฉํ•ด 2์ค‘ ๋ฐฐ์—ด์„ ๋™์ ํ• ๋‹นํ•˜์˜€์Šต๋‹ˆ๋‹ค. (vector<vector<long long>>dp(N + 1, vector<long long>(10));)
  • ๋งˆ์ง€๋ง‰ N์˜ ์˜ค๋ฅด๋ง‰ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ผ๋Š” ๊ฑด ์ˆ˜์˜ ๊ธธ์ด๊ฐ€ N ์ผ ๋•Œ, 0์œผ๋กœ ์‹œ์ž‘, 1๋กœ ์‹œ์ž‘, โ€ฆ , 9๋กœ ์‹œ์ž‘์˜ ๋ชจ๋“  ๊ฒฝ์šฐ์ด๋ฏ€๋กœ ์ด๋ฅผ ๊ฒฐ๊ด๊ฐ’์— ๋”ํ•ด์ฃผ์—ˆ์Šต๋‹ˆ๋‹ค.
  • MOD๋ผ๋Š” ์ƒ์ˆ˜๋ฅผ ๋งŒ๋“ค์–ด๋†“๊ณ  mod ์—ฐ์‚ฐ์„ ์ง„ํ–‰ํ–ˆ์Šต๋‹ˆ๋‹ค.

#include <iostream>
#include <algorithm>
#include <vector>
#define MOD 10007
using namespace std;
int main(void) {
	int N;
	cin >> N;
	vector<vector<long long>>dp(N + 1, vector<long long>(10));
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= 9; j++) dp[i][j] = 0;
	}
	for (int i = 0; i <= 9; i++) dp[1][i] = 1;
	for (int i = 2; i <= N; i++) {
		for (int j = 0; j <= 9; j++) {
			for (int k = j; k <= 9; k++) {
				dp[i][j] += dp[i - 1][k];
				dp[i][j] %= MOD;
			}
		}
	}
	int result = 0;
	for (int i = 0; i <= 9; i++) {
		result += dp[N][i];
		result %= MOD;
	}
	cout << result << '\n';
	return 0;
}