https://www.acmicpc.net/problem/2661
λ¬Έμ
μ«μ 1, 2, 3μΌλ‘λ§ μ΄λ£¨μ΄μ§λ μμ΄μ΄ μλ€. μμμ κΈΈμ΄μ μΈμ ν λ κ°μ λΆλΆ μμ΄μ΄ λμΌν κ²μ΄ μμΌλ©΄, κ·Έ μμ΄μ λμ μμ΄μ΄λΌκ³ λΆλ₯Έλ€. κ·Έλ μ§ μμ μμ΄μ μ’μ μμ΄μ΄λ€.
λ€μμ λμ μμ΄μ μμ΄λ€.
- 33
- 32121323
- 123123213
λ€μμ μ’μ μμ΄μ μμ΄λ€.
- 2
- 32
- 32123
- 1232123
κΈΈμ΄κ° NμΈ μ’μ μμ΄λ€μ Nμ리μ μ μλ‘ λ³΄μ κ·Έμ€ κ°μ₯ μμ μλ₯Ό λνλ΄λ μμ΄μ ꡬνλ νλ‘κ·Έλ¨μ μμ±νλΌ. μλ₯Ό λ€λ©΄, 1213121κ³Ό 2123212λ λͺ¨λ μ’μ μμ΄μ΄μ§λ§ κ·Έ μ€μμ μμ μλ₯Ό λνλ΄λ μμ΄μ 1213121μ΄λ€.
μ λ ₯
μ λ ₯μ μ«μ Nνλλ‘ μ΄λ£¨μ΄μ§λ€. Nμ 1 μ΄μ 80 μ΄νμ΄λ€.
μΆλ ₯
첫 λ²μ§Έ μ€μ 1, 2, 3μΌλ‘λ§ μ΄λ£¨μ΄μ Έ μλ κΈΈμ΄κ° NμΈ μ’μ μμ΄λ€ μ€μμ κ°μ₯ μμ μλ₯Ό λνλ΄λ μμ΄λ§ μΆλ ₯νλ€. μμ΄μ μ΄λ£¨λ 1, 2, 3λ€ μ¬μ΄μλ λΉμΉΈμ λμ§ μλλ€.
νμ΄
λ°±νΈλνΉ λ¬Έμ λ‘ μ¬κ·ν¨μλ₯Ό μ΄μ©νμ¬ 1μ΄λ 2λ 3μ μΆκ°ν κ²½μ°λ€μ λ€ μ΄ν΄λ³΄λ©΄λλ€
μ΄λ μ’μ μμ΄ νλ¨ κΈ°μ€μ ꡬννλκ² κ½€ κΉλ€λ‘μ λλ°, dpκ°λ μ μ μ©ν΄λ³΄μ.
μ΄μ μμ΄μ΄ μ’μ μμ΄μ΄μλ€λ©΄ μ΄ν μμ΄μ μΆκ°λ μ«μλΆλΆλ§ μ μΈνλ©΄ μ’μ μμ΄μ΄λ€. (μ΄ λΆλΆμ νλ¨ν νμ μμ)
맨 λ€ μ«μκ° ν¬ν¨λ λΆλΆμμ΄λ§ κ²ΉμΉλκ² μλμ§ νλ¨νλ©΄ λλ€.
λΆλΆμμ΄μ substrμ μ΄μ©νμ¬ κ΅¬ννμλ€.
// Authored by : seondal
// Co-authored by : -
// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
int n;
string ans;
bool isGood(string num, int cnt) {
for(int i=1; i<=cnt/2; i++) {
string s1 = num.substr(cnt-i, i);
string s2 = num.substr(cnt-i*2, i);
if(s1==s2)
return false;
}
return true;
}
void recur(string num, int cnt) {
// μ΄λ―Έ μλ£λμκ±°λ μ’μμμ΄μ΄ μλλΌλ©΄ ν¨μ€
if(ans!="")
return;
if(!isGood(num, cnt))
return;
// κ°―μ λ€ μ±μ μΌλ©΄ λ°ν
if(cnt == n) {
ans = num;
return;
}
// μ¬κ· (λ°±νΈλνΉ)
for(int i=0; i<n; i++) {
recur(num+"1", cnt+1);
recur(num+"2", cnt+1);
recur(num+"3", cnt+1);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
recur("", 0);
cout << ans;
return 0;
}
/*
*/
'ποΈ ICPC Sinchon > Backtracking' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[BOJ][C++] λ°±μ€ 14888λ²: μ°μ°μ λΌμλ£κΈ° (0) | 2023.07.06 |
---|---|
[BOJ][C++] λ°±μ€ 15811λ²: 볡면μ°?! (0) | 2023.01.22 |
[BOJ][C++] λ°±μ€ 2580λ²: μ€λμΏ (0) | 2023.01.22 |
[BOJ][C++] λ°±μ€ 23304λ²: μμΉ΄λΌμΉ΄ (0) | 2023.01.21 |
[BOJ S2][C++] λ°±μ€ 10971λ²: μΈνμ μν 2 (0) | 2022.09.27 |