❮
π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μ΄ νμν λ¬Έμ