โ๋ฌธ์
https://www.acmicpc.net/problem/1904
๋ฉ๋ชจ๋ฆฌ: 22248 KB, ์๊ฐ: 116 ms
๋ค์ด๋๋ฏน ํ๋ก๊ทธ๋๋ฐ
์ง์์ด์๊ฒ 2์ง ์์ด์ ๊ฐ๋ฅด์ณ ์ฃผ๊ธฐ ์ํด, ์ง์์ด ์๋ฒ์ง๋ ๊ทธ์๊ฒ ํ์ผ๋ค์ ์ ๋ฌผํด์ฃผ์
จ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด ๊ฐ๊ฐ์ ํ์ผ๋ค์ 0 ๋๋ 1์ด ์ฐ์ฌ ์๋ ๋ฑ์ฅ์ ํ์ผ๋ค์ด๋ค.
์ด๋ ๋ ์ง๊ถ์ ๋์ฃผ๊ฐ ์ง์์ด์ ๊ณต๋ถ๋ฅผ ๋ฐฉํดํ๊ธฐ ์ํด 0์ด ์ฐ์ฌ์ง ๋ฑ์ฅ์ ํ์ผ๋ค์ ๋ถ์ฌ์ ํ ์์ผ๋ก ์ด๋ฃจ์ด์ง 00 ํ์ผ๋ค์ ๋ง๋ค์๋ค. ๊ฒฐ๊ตญ ํ์ฌ 1 ํ๋๋ง์ผ๋ก ์ด๋ฃจ์ด์ง ํ์ผ ๋๋ 0ํ์ผ์ ๋ ๊ฐ ๋ถ์ธ ํ ์์ 00ํ์ผ๋ค๋ง์ด ๋จ๊ฒ ๋์๋ค.
๊ทธ๋ฌ๋ฏ๋ก ์ง์์ด๋ ํ์ผ๋ก ๋ ์ด์ ํฌ๊ธฐ๊ฐ N์ธ ๋ชจ๋ 2์ง ์์ด์ ๋ง๋ค ์ ์๊ฒ ๋์๋ค. ์๋ฅผ ๋ค์ด, N=1์ผ ๋ 1๋ง ๋ง๋ค ์ ์๊ณ , N=2์ผ ๋๋ 00, 11์ ๋ง๋ค ์ ์๋ค. (01, 10์ ๋ง๋ค ์ ์๊ฒ ๋์๋ค.) ๋ํ N=4์ผ ๋๋ 0011, 0000, 1001, 1100, 1111 ๋ฑ ์ด 5๊ฐ์ 2์ง ์์ด์ ๋ง๋ค ์ ์๋ค.
์ฐ๋ฆฌ์ ๋ชฉํ๋ N์ด ์ฃผ์ด์ก์ ๋ ์ง์์ด๊ฐ ๋ง๋ค ์ ์๋ ๋ชจ๋ ๊ฐ์ง์๋ฅผ ์ธ๋ ๊ฒ์ด๋ค. ๋จ ํ์ผ๋ค์ ๋ฌดํํ ๋ง์ ๊ฒ์ผ๋ก ๊ฐ์ ํ์.
โ๐ปํ์ด
'00'ํ์ผ๊ณผ '1'ํ์ผ๋ง์ ์ด์ฉํ์ฌ 2์ง ์์ด์ ๋ง๋ค ์ ์์. ์ฆ, '01', '10'์ ๋ง๋ค ์ ์์.
N = 1์ผ ๋, '1'๋ง ๊ฐ๋ฅ. N = 2์ผ ๋, '00', '11' 2๊ฐ ๊ฐ๋ฅ.
N = 3์ผ ๋, '100', '001', '111' 3๊ฐ ๊ฐ๋ฅ.
์ด ๋, N = 3์ธ ๊ฒฝ์ฐ๋ฅผ ๋ณด๋ฉด '1'๊ณผ '11', '00'์ผ๋ก ์กฐํฉํ๋ค๊ณ ์๊ฐํ ์ ์์.
๊ทธ๋ฌ๋ฏ๋ก dp[3] = dp[2] + dp[1]์ด๋ผ๊ณ ์๊ฐํ ์ ์์.
i๋ก ๋ฐ๊ฟ๋ณด๋ฉด dp[i] = dp[i - 1] + dp[i - 2]๋ผ๊ณ ํ ์ ์์.
๐ป์ฝ๋
import java.io.*;
public class Main {
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
long[] dp = new long[1000001];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++)
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
bw.write(String.valueOf(dp[n]));
bw.flush();
bw.close();
br.close();
}
}
'Coding Test > Algorithms' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] ํ๋ฐฐ์์/Java - Lv.2 (0) | 2024.10.24 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] ํ ์ธํ์ฌ/Java - Lv.2 (0) | 2024.10.21 |
[Baekjoon] 9461.ํ๋๋ฐ ์์ด/Java - Silver3 (0) | 2024.10.15 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๊ฐ์ฅ ํฐ ์/Java - Lv.2 (0) | 2024.10.10 |
[ํ๋ก๊ทธ๋๋จธ์ค] ์ด์ค์ฐ์ ์์ํ/Java - Lv.3 (0) | 2024.10.10 |