백준 14238, 출근 기록

개요

문제 링크
골드 3, DP, Greedy
1칸, 2칸, 3칸마다 존재 가능한 A,B,C를 이용한 문자열 구성

---

접근

1. 분류는 DP인데 Greedy로 풀 수 있을 것 같아서 시도해봤음. 계속 1%컷나서 재귀쓰는 DP로 시도해봄, 또 1%컷 나서 결국 질문게시판을 둘러보다가 메모이제이션하고 백트래킹 이용한 풀이가 내 풀이랑 너무 다른 것을 확인했다. 다른 사람 풀이 읽는 것은 최소한으로 하려 했는데 달라도 너무 달라서 읽고 이해했음.
   Greedy 풀이는 조건 하나가 빠져있어서 틀린 거였음. Greedy 풀이도 다른 사람 풀이 읽으면서 이해했다. 아직 골3 풀 때가 아닌가...
2. 정해는 메모이제이션 & 백트래킹인 것 같아 DP부터 알아보자.

---

1) DP

1. 재귀문을 이용해서 풀이를 짜다보면 a,b,c의 개수를 입력으로 해야 하는 건 쉽게 생각할 수 있다.
2. 백트래킹이란?
   1. 가능한 경우만 재귀문을 돌리는 것인데, 고려해야 할 요소는 3가지이다. 출력, 입력, 다음단계.
   2. 먼저 "가능"을 어떻게 판단하냐, 이 상태에서 끝까지 문자열을 구성할 수 있는가 를 판단하면 된다. 그럼 while 같은 반복문을 써야 하나? 아니다. 재귀문으로 다음 단계가 가능한지만 판단하면 알아서 재귀적으로 끝까지 판단해준다.
      즉, 재귀함수의 출력은 현재 상태의 가능여부 이다. 비슷한 문제로 2239 스도쿠가 있다.
   3. 백트래킹의 다음단계란 무엇일까. 현재 상태에서 A,B,C를 추가한 경우의 가능여부이다. B의 추가 조건은 이전 값이 B가 아닌것, C의 추가 조건은 이전값과 전전값이 C가 아닌 것이다.
      즉 재귀함수의 입력은 A개수, B개수, C개수, 이전값, 전전값이 된다.
3. 메모이제이션은? 사실 DP의 근본적인 존재 여부이다. 재귀문에서 한 번 스캔했던 경우는 다시 안 봐야 시간 절약이 되는데, 이 기능을 한다. 재귀문의 모든 입력을 하나의 상태로 보고 저장하고 이미 탐색했던 경우라면 가능여부 = 0으로 return한다.
4. 입력이 5개이므로 5차원 배열을 이용해도 되지만, 더 단순화하기에는 map이 좋은 것 같아서 map을 써봤다.
5. 결론은? a,b,c를 세고, 재귀문 입력으로 넣은 뒤, 현재 자리에 A를 넣고 다음단계 (a-1,b,c)가 가능하면 true, B를 넣고 다음단계 (a,b-1,c)가 가능하면 true, C를 넣고 다음단계 (a,b,c-1)이 가능하면 true를 내보낸다.

---

2) Greedy

1. 그리디한 인간이 되어보자. C가 가장 까다로우니 CBA 순으로 넣어준다. 우선 C가 들어갈 조건은 c의 개수가 남아있고, 전값과 전전값이 C가 아닌 경우이다. B가 들어갈 조건은 b의 개수가 남아있고, 전값이 B가 아닌 경우이다.

2. 그러면 이런 조건을 만족할 때만 ABC를 각각 넣어주면 되는 것인가? 아니다. 하나의 조건이 더 필요하다. 테케에도 있는 예시인데,

   BBC
   output : CBX -> -1
   answer : BCB

3. 위 예시에 -1이 출력되어버린다. C를 먼저 출력해서는 안됐다. 처음에는 이런 경우가 길이 3짜리 B2 C1만 있는줄 알고 BCB를 출력했다. 하지만 아래 케이스를 보자.

   CCBBBA
   output : CBACBX -> -1
   answer : CBABCB

   BBC가 남게되는 상황도 고려해야 한다. 그럼 BBC만 남게 되는 상황을 고려하면 모두 커버가 될까? 아니다. 아래 케이스를 또 보자.

   CCBBBBA
   output : CBACBXX -> -1
   answer : BCBABCB

   그러면 찐막으로 B부터 시작하는 경우를 만들면 어떨까? 안된다. 아래 케이스를 보자.

   CCCBBBBBBAA
   output : BCBACBACBXX -> -1
   answer : BCBABCBABCB

   핵심은 무엇이냐, CBA순으로 넣어주다보면 CBA만을 자유로운 덩어리로 취급한다. 하지만 CBAB등의 덩어리도 고려해야 한다. 그래서 CBA 다음에 C가 올 것인지 B가 올 것인지를 고려해야 한다. 결론은 제대로 된 선택을 하려면 BBC등의 특수케이스를 고려할 것이 아니라 C를 선택하는 조건을 다시 생각해봐야 하는 것이었다.

4. 그리디한 인간이 덩어리를 선택할 때, 최적의 덩어리는 CBAB이다. 왜냐? CBAC보다 문제 없이 B를 더 쓸 수 있기 때문.
   CBAB등의 덩어리를 위해 C자리에 대신 B가 와야 하는 경우를 생각해보자. 우선 앞에 B가 있으면 안되고, 남은 자리에 B가 절반이 넘게 들어가면 안된다. 즉 남은 B의 개수가 남은 길이의 절반 초과일 때 B를 넣어준다.

   따라서 그리디 풀이는 CBA 순으로 선택하는데, 이전값이 B가 아니고, 남은 B가 잔여 길이의 절반 초과이면 B를 우선 선택한다. 앞에 not을 붙여서 C의 조건에 추가해주면 된다.

---

Pseudo code

// dp
func(state(a,b,c,prev,prevprev)) {
    if (a=0 && b=0 && c=0)
        return 1 // end
    if (memo[state])
        return 0
    memo[state] = 1
    if (condition_of_c)
        // if next is available
        // prev become prevprev
        if (func(a,b,c-1,'C',prev))
            return 1
    if (condition_of_b)
        if (func(a,b-1,c,'B',prev))
            return 1
    if (condition_of_a = a>0)
        if (func(a-1,b,c,'A',prev))
            return 1
    return 0
}

// greedy
prefer_b = string[i-1]!='B' && b > (n-i)/2

for (i = 0~n)
    if (condition_of_c && !prefer_b)
        string[i] = 'C'
    else if (condition_of_b)
        string[i] = 'B'
    else
        string[i] = 'A'

---

Source code

// dp
#include <bits/stdc++.h>
using namespace std;

const int N = 55;
string s, ans;
int n, ca, cb, cc;

typedef array<int,5> state;
map <state,int> dp;

int make(int a, int b, int c, char p1, char p2) {
    if (!a && !b && !c)
        return 1;
    if (dp[{a,b,c,p1,p2}])
        return 0;
    dp[{a,b,c,p1,p2}] = 1;

    ans[n-(a+b+c)] = 'C';
    if (c && p1!='C' && p2!='C')
        if (make(a,b,c-1,'C',p1))
            return 1;
    ans[n-(a+b+c)] = 'B';
    if (b && p1!='B')
        if (make(a,b-1,c,'B',p1))
            return 1;
    ans[n-(a+b+c)] = 'A';
    if (a)
        if (make(a-1,b,c,'A',p1))
            return 1;
    return 0;
}

int main() {
    cin >> s;
    n = s.size();
    ans.resize(n);
    for (int i=0; i<n; i++)
        if (s[i]=='A')
            ca++;
        else if (s[i]=='B')
            cb++;
        else
            cc++;
    cout << (make(ca,cb,cc,'A','A')?ans:"-1");
}

// greedy
#include <iostream>
using namespace std;

string s, p;
int n, a, b, c;

int main() {
    cin >> s;
    n = s.size();
    for (int i=0; i<n; i++)
        if (s[i]=='A')
            a++;
        else if (s[i]=='B')
            b++;
        else
            c++;
    p = "AA";
    int cb, cc, pb;
    for (int i=2; i<n+2; i++) {
        cc = p[i-1]!='C'&&p[i-2]!='C'&&c;
        cb = p[i-1]!='B'&&b;
        pb = p[i-1]!='B'&&(n-i+1)/2<b;
        if (cc&&!pb)
            p.push_back('C'), c--;
        else if (cb)
            p.push_back('B'), b--;
        else if (a)
            p.push_back('A'), a--;
    }
    p = p.substr(2,n+2);
    if (p.size()<n)
        cout << -1;
    else
        cout << p;
}