[BOJ/12969/Golang] 백준 12969 - ABC

접근 방식

앞선 포스트에서 소개한 14238번 문제인 '출근 기록' 문제와 유사한 문제입니다.

문제의 조건

1. 하루에 한 명씩 출근한다.
2. 문자열의 길이 = 출근 기록의 길이(N)
3. A는 본인 스스로 짝을 이룰 수 없다.
4. B는 A와 짝을 이룰 수 있다.
5. C는 A, B 모두와 짝을 이룰 수 있다.

반드시 필요한 조건만 정리해보면, 문자열의 길이인 i가 필요합니다. 또한 A가 몇 개 있는지, B가 몇 개 있는지, C가 몇 개 있는지 알아야 합니다. 마지막으로 쌍의 개수를 계속 체크해주어야 하므로, 쌍의 개수도 나타나야 합니다.

그런데 여기에서 변수를 하나 줄일 수 있습니다. 바로 C인데요. C의 개수는 전체 문자열의 길이에서 A의 개수와 B의 개수를 빼준 크기입니다. 따라서, 실질적으로 사용하게 되는 변수는 문자열의 길이, A의 개수, B의 개수, 쌍의 개수 입니다.

점화식

위 조건을 가지고 상황을 표현하는 점화식을 세워보면 아래와 같습니다.

D[i][a][b][p] = 문자열의 길이가 i일 때, A는 a개, B는 b개이며
                문제의 조건을 만족하는 쌍의 개수가 p인 상황의 가능 여부

여기에서 D의 값은 {0, 1} 중 하나입니다.
D == 0 이면, 아직 방문하지 않은 노드임을 의미합니다.
D == 1 이면, 해당 노드를 이미 방문했음을 의미합니다.
또한, 마지막까지 1이 되는 경우는 해당 조건이 참임을 의미합니다.

마지막에 A를 추가하는 경우

길이가 i이고, A가 a개, B가 b개, 쌍이 p개 있는 상태는 D[i][a][b][p]로 나타낼 수 있습니다.

이 상태에서 A를 새로 추가한다면 다음과 같은 식을 세울 수 있습니다.

D[i+1][a+1][b][p]

길이는 A를 한 개 추가함으로써 i → i+1이 됩니다.

A의 개수도 A를 한 개 추가하였으므로 a → a+1이 됩니다.

A는 그 누구와도 쌍을 이루지 못하기 때문에 쌍의 개수 p는 증가하지 않습니다.

마지막에 B를 추가하는 경우

D[i+1][a][b+1][p+a]

길이는 B를 한 개 추가하였으므로 i → i+1이 됩니다.

B의 개수도 B가 한개 추가되었으므로 b → b+1이 됩니다.

그리고 B는 A의 개수만큼 새로운 쌍을 만들어낼 수 있으므로, 쌍의 개수 p는 p+a가 됩니다.

마지막에 C를 추가하는 경우

D[i+1][a][b][p+a+b]

길이는 C를 한 개 추가하였으므로 i → i+1이 됩니다.

C의 개수는 현재 점화식에서 사용하지 않으므로 나타나지 않습니다. 다만 i+1-a-b 개임을 알 수 있습니다.

C는 A와 B 모두 쌍을 이룰 수 있으므로, A의 개수와 B의 개수만큼 쌍이 새로 만들어집니다. 따라서 쌍의 개수는 p → p+a+b 가 됩니다.

재귀함수로 풀이

func solve(idx, a, b, p int) int {
    if idx == N {
        if p == K {
            return 1
        }
        return 0
    }
    if D[idx][a][b][p] == 1 {
        return 0
    }
    // 방문 처리
    D[idx][a][b][p] = 1

    // A를 넣어본다.
    ans[idx] = 'A'
    if solve(idx+1, a+1, b, p) == 1 {
        return 1
    }

    // B를 넣어본다.
    ans[idx] = 'B'
    if solve(idx+1, a, b+1, p+a) == 1 {
        return 1
    }

    // C를 넣어본다.
    ans[idx] = 'C'
    if solve(idx+1, a, b, p+a+b) == 1 {
        return 1
    }
    return 0
}

풀이는 재귀함수로 작성하면 위와 같습니다.

종료 조건

    if idx == N {
        if p == K {
            return 1
        }
        return 0
    }

함수의 종료 조건은 문자열의 길이만큼 인덱스가 이동하였을 때, 우리가 원하는 만큼의 쌍의 개수가 만들어졌다면, 참으로 리턴합니다. 그렇지 않다면 불가능하다는 의미로 0을 리턴합니다.

Memoization 활용

    if D[idx][a][b][p] == 1 {
        // 이미 방문한 적이 있는데, 다시 방문했다는 건 해당 노드가 답이 아니라는 뜻
        return 0 
    }
    // 방문 처리
    D[idx][a][b][p] = 1

memoization을 활용하기 위해 이미 방문한 적이 있는 노드인지 체크합니다. 이미 방문한 노드를 다시 방문한다는 것은 해당 노드가 정답이 아니었다는 것을 의미하므로, 불가능하다는 의미로 0을 리턴합니다. 여기에서 D의 값이 방문 여부를 의미하기도 하고, 정답 여부를 의미하기도 하므로, 헷갈리지 않도록 주의합니다.

실제 연산

이후 나오는 3개의 조건문은 A와 B, C를 추가하고 해당 상황이 가능한지 확인합니다.

    // A를 넣어본다.
    ans[idx] = 'A'
    if solve(idx+1, a+1, b, p) == 1 {
        return 1
    }

    // B를 넣어본다.
    ans[idx] = 'B'
    if solve(idx+1, a, b+1, p+a) == 1 {
        return 1
    }

    // C를 넣어본다.
    ans[idx] = 'C'
    if solve(idx+1, a, b, p+a+b) == 1 {
        return 1
    }

각각의 조건문에서는 위에서 설명한 A를 추가했을 때의 상황, B를 추가했을 때의 상황, C를 추가했을 때의 상황이 가능한 상황인지 체크하고 가능한 상황이면 1을 리턴합니다. 이 때 정답을 출력하기 위해 rune slice인 ans 슬라이스를 계속 채워나갑니다.

    return 0

만약 위 3 개의 연산에서 모두 불가능하였다면, 해당 노드는 조건을 만족할 수 없는 상태입니다. 따라서 불가능하다는 의미로 0을 리턴합니다.

코드

package main

import (
    "bufio"
    "fmt"
    "os"
)

var (
    w = bufio.NewWriter(os.Stdout)
    r = bufio.NewReader(os.Stdin)
)

var (
    N, K int
    D    [31][31][31][436]int
    ans  []rune
)

func main() {
    defer w.Flush()
    fmt.Fscanf(r, "%d %d\n", &N, &K)
    ans = make([]rune, N+1)
    if solve(0, 0, 0, 0) == 1 {
        fmt.Fprintln(w, string(ans))
    } else {
        fmt.Fprintln(w, -1)
    }
}

func solve(idx, a, b, p int) int {
    if idx == N {
        if p == K {
            return 1
        }
        return 0
    }
    if D[idx][a][b][p] == 1 {
        return 0
    }
    D[idx][a][b][p] = 1

    ans[idx] = 'A'
    if solve(idx+1, a+1, b, p) == 1 {
        return 1
    }

    ans[idx] = 'B'
    if solve(idx+1, a, b+1, p+a) == 1 {
        return 1
    }

    ans[idx] = 'C'
    if solve(idx+1, a, b, p+a+b) == 1 {
        return 1
    }
    return 0
}

마무리

여담으로 D 배열의 값이 0과 1만을 사용하기 때문에 bool 자료형을 사용할 수도 있습니다. 제 경우 bool 자료형을 사용했을 때 메모리도 적게 들고, 수행 시간도 절반 가량 짧게 나왔습니다. bool 자료형도 이용해 보세요!

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊