πŸ•οΈ ICPC Sinchon/Backtracking

[BOJ][C++] λ°±μ€€ 2661번: μ’‹μ€μˆ˜μ—΄

선달 2023. 1. 22. 04:58
λ°˜μ‘ν˜•

https://www.acmicpc.net/problem/2661

 

2661번: μ’‹μ€μˆ˜μ—΄

첫 번째 쀄에 1, 2, 3으둜만 이루어져 μžˆλŠ” 길이가 N인 쒋은 μˆ˜μ—΄λ“€ μ€‘μ—μ„œ κ°€μž₯ μž‘μ€ 수λ₯Ό λ‚˜νƒ€λ‚΄λŠ” μˆ˜μ—΄λ§Œ 좜λ ₯ν•œλ‹€. μˆ˜μ—΄μ„ μ΄λ£¨λŠ” 1, 2, 3λ“€ μ‚¬μ΄μ—λŠ” λΉˆμΉΈμ„ 두지 μ•ŠλŠ”λ‹€.

www.acmicpc.net

 

문제

숫자 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;
}

/*
 */
λ°˜μ‘ν˜•