โฎ
๐2661๋ฒ: ์ข์์์ด
20161019
(๋ญ๊ฐ ์ข๋ค๋ ๊ฑด์ง๋ ๋ชจ๋ฅด๊ฒ ์ง๋ง)
๋ฌธ์ ๋ฅผ ์ฝ์ด๋ณด๋ฉด ๋ฐฑํธ๋ํน์ ํ๋ฉด 100% ํ๋ฆฐ๋ค๋ ๊ฒ์ ํ์คํ์ง๋ง N = 80 ์ด๋ผ
๊ทธ๋ฅ ์์ผ๋ก ํด๋ณด๊ณ ์ถ๋ค๋ ์๊ฐ์ด ๋ ๋ค.
๋ ๊ฐ์ง ์กฐ๊ฑด์ ๋ง์กฑ ์์ผ์ผ ํ๋ค.
1. ์ธ์ ํ ๋ ๊ฐ์ ์์ด์ด ๊ฐ์ง ์์ผ๋ฉด์
2. ์ ์๋ก ๋ํ๋์ ๋ ๊ฐ์ฅ ์๊ฐ ์๋๋ก ๋ง๋ค์ด ์ฃผ์ด์ผํ๋ค.
2๋ฒ ์กฐ๊ฑด์ ์ํด์๋ ์์ชฝ์ ์์ ์๊ฐ ์ค๋๋ก ํด์ผ ํ๋ค.
๋ฐ๋ผ์ ๊ธธ์ด๊ฐ i์ธ ๊ฐ์ฅ ์์ ์ข์ ์์ด์ S(i) ๋ผ๊ณ ํ๋ฉด
S(1) = 1 ์ด๋ค.
i = 2์ผ๋์๋ 1๋ฒ ์กฐ๊ฑด์ ์ํด 11์ ๋ ์ ์๊ณ ๊ทธ ๋ค์ ์์ ์์ธ 12๊ฐ ๋๋ค.
๊ณ์ํด์ S(i-1) ์ ๋งจ ๋ค์ 1 2 3 ์์๋๋ก ๋ฃ์ด๋ณด๋ฉด์ 1. 2. ๋ฒ ์กฐ๊ฑด์ ๋ง์กฑ ์ํค๋ ์๋ฅผ ์ฐพ์ผ๋ฉด ์ข์์์ด์ ๊ณ์ ์ฐพ์๋๊ฐ ์ ์๋ค.
S(2) = 12
S(3) = 121
S(4) = 1213
S(5) = 12131
S(6) = 121312
S(7) = 1213121
์ด ๋ฐฉ๋ฒ์ i = 8 ์ผ๋ ๋งํ๊ฒ ๋๋๋ฐ
12131211 12131212 12131213 ๋ชจ๋ 1๋ฒ ์กฐ๊ฑด์ ๋ง์กฑ์ํค์ง ๋ชปํ๋ค.
์ฌ๊ธฐ์ ๋ง๋งํ์ง๋ง ์ฐจ๊ทผ์ฐจ๊ทผ ๋์๊ฐ์ ์๊ฐํด๋ณด๋ฉด
i = 7 ์ผ๋ 1213121 ๋์ 1213123 ์ด ๊ฐ๋ฅํจ์ ์ ์ ์๋ค.
๋ฐ๋ผ์
S(8) = 1213123 1
S(9) = 1213123 12
S(10) = 1213123 121
S(11) = 1213123 1213
S(12) = 1213123 12131
S(13) = 1213123 121312
S(14) = 1213123 1213121
i = 15 ์ผ ๋ ์๊น์ ๋ง์ฐฌ๊ฐ์ง๋ก
S(15) = 1213123 1213123 1 ์ ํ๊ฒ ๋๋ฉด ๋ 1๋ฒ ์กฐ๊ฑด์ ๋ง์กฑ์ํค์ง ๋ชปํ๋ค.
........
.......
์ฌ๊ธฐ๊น์ง๋ง ํ์.
์ฌ๊ธฐ์ ๊ท์น์ฐพ๊ธฐ๋ฅผ ํฌ๊ธฐํ๊ณ ๋ฐฑํธ๋ํน์ ํ๊ธฐ๋ก ๊ฒฐ์ฌ.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n,a['ae'];
void dfs(int here)
{
for(int i = 1; i <= here/2 ; i++)
{
if(equal(a+here-i, a+here, a+here-i-i)) return;
}
if(here == n)
{
for(int i = 0; i < n ; i++)
cout<<a[i];
cout<<'\n';
exit(0);
}
for(int candi = 1 ; candi <= 3; candi++)
{
a[here] = candi;
dfs(here+1);
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}
|
equal(f1, l1, f2)๋ f1๊ฐ l1๊น์ง ์ฆ๊ฐํ๋ ๋์ f2๋ ์ฆ๊ฐํ ๋ f1, f2๊ฐ ๊ฐ๋ฆฌํจ ๋ ์์ด์ด ๊ฐ์์ง ์ฌ๋ถ๋ฅผ ๋ฆฌํดํ๋ค.
์ด์ํ๊ฒ equal๋ก๋ ์๋๋๋ฐ strncmp๋ก ํ๋ ค๊ณ ํ๋ฉด WA๊ฐ ๋์จ๋ค.
Upsolving์ด ํ์ํ ๋ฌธ์