접근 방식
이 문제는 앞으로 정리할 문제인 12969번의 ABC 문제와 유사한 문제입니다. 아무리 생각해도 점화식이 떠오르지 않아 강의를 듣고 이해한 내용을 정리해봅니다.
문제의 조건
- 하루에 한 명씩 출근한다.
- 문자열의 길이 = 출근 기록의 길이(N)
- A는 매일 출근이 가능하다.
- B는 출근한 다음 날에는 쉬어야 한다.
- C는 출근한 다음 날과 다다음 날은 쉬어야 한다.
반드시 필요한 조건만 정리해보면, A가 출근한 횟수, B가 출근한 횟수, C가 출근한 횟수가 필요합니다. 또한 B와 C처럼 전날과 전전날의 출근자를 알아야만 상황이 정의되는 사람을 표현하기 위해 전날 출근자(P1)와 전전날 출근자(P2)의 정보도 필요합니다.
참고로 12969번 ABC 문제는 전체 문자열의 길이를 알고 A와 B의 개수가 정해지면 C는 자동으로 정해지는 패턴이어서 (C = N - (A+B)) C가 점화식의 조건으로 포함되지 않았습니다. 대신 문자열의 길이를 조건으로 추가해서 점화식을 구했습니다.
점화식
위 조건을 가지고 상황을 표현하는 점화식을 세워보면 아래와 같습니다.
D[a][b][c][p1][p2] = A가 a번, B가 b번, C가 c번 출근했고,
전날에 p1이, 전전날에 p2가 출근하는 상황의 가능 여부
(단, p1과 p2에서 A를 0, B를 1, C를 2로 표현한다)
// 여기에서 D의 값은 {-1, 0, 1} 중 하나입니다.
// D == -1 이면, 아직 방문하지 않은 노드임을 의미합니다.
// D == 0 이면, 해당 노드는 조건을 만족하지 못함을 의미합니다.
// D == 1 이면, 해당 노드가 조건을 만족함을 의미합니다.오늘 A가 출근하는 경우
오늘 A가 출근하는 경우가 가능한지 알아보려면 다음과 같은 식이 세워집니다.
D[a+1][b][c][0][p1]
다만 여기에서 이해가 가지 않는 부분은, 오늘 A가 출근하는데 왜 전날을 의미하는 P1 자리에 A가 들어가야하는 것인지가 이해가 가지 않습니다. 이 부분은 질문에 대한 답변이 온 이후에 업데이트하도록 하겠습니다.
우선 나머지 경우에 대해서도 이 점화식이 이해가 되었다는 가정 하에 세워보도록 하겠습니다.
오늘 B가 출근하는 경우
B가 오늘 출근하려면, 전날엔 B가 출근해선 안됩니다.
따라서 식을 세워보면 다음과 같습니다.
D[a][b+1][c][1][p1] && p1 != 1
오늘 C가 출근하는 경우
C가 오늘 출근하려면, 전날과 전전날엔 C가 출근해선 안됩니다.
따라서 식을 세워보면 다음과 같습니다.
D[a][b][c+1][2][p1] && p1 != 2 && p2 != 2
재귀함수로 풀이
func solve(a, b, c, p1, p2 int) int {
temp := &D[a][b][c][p1][p2]
if a+b+c == N {
return 1
}
if *temp != -1 {
return *temp
}
if a+1 <= A {
if solve(a+1, b, c, 0, p1) == 1 {
*temp = 1
return *temp
}
}
if b+1 <= B && p1 != 1 {
if solve(a, b+1, c, 1, p1) == 1 {
*temp = 1
return *temp
}
}
if c+1 <= C && p1 != 2 && p2 != 2 {
if solve(a, b, c+1, 2, p1) == 1 {
*temp = 1
return *temp
}
}
*temp = 0
return *temp
}풀이는 재귀함수로 작성하면 위와 같습니다.
종료 조건
if a+b+c == N {
return 1
}우선 이 함수의 종료 조건은 A와 B, C가 총 N번 출근하게 될 때 입니다. 출근 기록부에 적힌 횟수보다 많을 수 없기 때문입니다.
Memoization 활용
if *temp != -1 {
return *temp
}memoization을 활용하기 위해 D의 값이 -1인지 확인합니다. -1이라면 아직 방문하지 않은 노드에 온 것이므로, 함수를 진행합니다. 만약 -1이 아니라면 값이 이미 있으므로, 해당 값을 리턴합니다.
실제 연산
이후 나오는 3개의 조건문은 A와 B, C가 나올 수 있는지 확인하는 연산을 수행합니다.
if a+1 <= A {
if solve(a+1, b, c, 0, p1) == 1 {
*temp = 1
return *temp
}
}우선 A가 하루 더 일할 수 있는지 체크합니다. 만약 일할 수 있다면, A는 어떠한 조건 없이 출근할 수 있으므로, 바로 다음 재귀로 들어갑니다. 그리고 해당 재귀를 통해 얻은 값이 '가능'이면, 현재의 조건도 참이 되어 가능으로 반환할 수 있습니다.
if b+1 <= B && p1 != 1 {
if solve(a, b+1, c, 1, p1) == 1 {
*temp = 1
return *temp
}
}다음으로는 B가 하루 더 일할 수 있는지 체크합니다. 그리고 B는 전날에 출근해서는 안되므로, p1 != 1 의 조건이 추가됩니다. 이후는 A와 마찬가지 방법으로 가능 여부를 기록해줍니다.
if c+1 <= C && p1 != 2 && p2 != 2 {
if solve(a, b, c+1, 2, p1) == 1 {
*temp = 1
return *temp
}
}마지막으로는 C가 하루 더 일할 수 있는지 체크합니다. C는 전날과 전전날에 출근해서는 안되므로, p1 != 2 && p2 != 2 조건이 추가됩니다. 이후는 A와 B에서 했던 것처럼 가능 여부를 체크하여 기록합니다.
*temp = 0
return *temp만약 위 3 개의 연산에서 모두 불가능하였다면, 해당 노드는 조건을 만족할 수 없는 상태입니다. 따라서 가능 여부에 불가능으로 기록해줍니다.
출력 함수
문제에서는 가능 여부를 출력하라고 한 것이 아니라 가능한 출근 기록 중에 아무거나 하나를 출력해달라고 했습니다. 따라서 우리가 만든 memoization 배열을 가지고 가능한 출근자들을 한 명씩 출력하면 됩니다.
func makeAnswer(a, b, c, p1, p2 int) string {
if a+b+c == N {
return ""
}
if a+1 <= A && solve(a+1, b, c, 0, p1) == 1 {
return "A" + makeAnswer(a+1, b, c, 0, p1)
}
if b+1 <= B && p1 != 1 {
if solve(a, b+1, c, 1, p1) == 1 {
return "B" + makeAnswer(a, b+1, c, 1, p1)
}
}
if c+1 <= C && p1 != 2 && p2 != 2 {
if solve(a, b, c+1, 2, p1) == 1 {
return "C" + makeAnswer(a, b, c+1, 2, p1)
}
}
return ""
}출력 함수는 재귀 함수와 매우 유사합니다. 다만 재귀 함수에서는 우리가 가능한 순서를 모두 체크해두기 위함이 목적이었다면, 이 출력 함수는 가능한 순열 중에 하나를 생성해서 리턴해주는 것이 목적입니다.
재귀 함수의 종료 조건과 마찬가지로 이 함수 또한 종료 조건은 A와 B, C가 출근할 수 있는 날을 모두 사용한 경우입니다. 해당 시점에는 더 출근할 사람이 없으므로 끝에 ""을 추가하여 더 일할 사람이 없음을 표기해줍니다.
이후에 나오는 연산은 재귀 함수에서 본 것과 유사합니다. A가 더 일할 수 있다면, A를 앞에 추가해주고, 이후에 올 순서는 출력 함수를 재귀적으로 수행하여 구해냅니다. 여기에서 solve() 함수를 또 사용하기 때문에 시간 복잡도가 증가하는 것이 아닌지 생각해볼 수도 있겠지만, 우리는 앞서 solve() 함수를 작성할 때 memoization을 활용하도록 만들어뒀으므로, 이미 구해둔 값을 그대로 리턴할 것이기 때문에 해당 부분은 염려하지 않아도 괜찮습니다.
A와 유사하게 B와 C도 연산하여 가능한 출근 기록 문자열을 생성하여 최종 리턴합니다.
코드
package main
import (
"bufio"
"fmt"
"os"
"strings"
)
var (
w = bufio.NewWriter(os.Stdout)
sc = bufio.NewScanner(os.Stdin)
)
var (
A, B, C, N int
D [51][51][51][3][3]int
)
func main() {
defer w.Flush()
for i := range D {
for j := range D[i] {
for k := range D[i][j] {
for l := range D[i][j][k] {
for m := range D[i][j][k][l] {
D[i][j][k][l][m] = -1
}
}
}
}
}
countString()
if solve(0, 0, 0, 0, 0) == 1 {
fmt.Fprintln(w, makeAnswer(0, 0, 0, 0, 0))
} else {
fmt.Fprintln(w, -1)
}
}
func makeAnswer(a, b, c, p1, p2 int) string {
if a+b+c == N {
return ""
}
if a+1 <= A && solve(a+1, b, c, 0, p1) == 1 {
return "A" + makeAnswer(a+1, b, c, 0, p1)
}
if b+1 <= B && p1 != 1 {
if solve(a, b+1, c, 1, p1) == 1 {
return "B" + makeAnswer(a, b+1, c, 1, p1)
}
}
if c+1 <= C && p1 != 2 && p2 != 2 {
if solve(a, b, c+1, 2, p1) == 1 {
return "C" + makeAnswer(a, b, c+1, 2, p1)
}
}
return ""
}
func solve(a, b, c, p1, p2 int) int {
temp := &D[a][b][c][p1][p2]
if a+b+c == N {
return 1
}
if *temp != -1 {
return *temp
}
if a+1 <= A {
if solve(a+1, b, c, 0, p1) == 1 {
*temp = 1
return *temp
}
}
if b+1 <= B && p1 != 1 {
if solve(a, b+1, c, 1, p1) == 1 {
*temp = 1
return *temp
}
}
if c+1 <= C && p1 != 2 && p2 != 2 {
if solve(a, b, c+1, 2, p1) == 1 {
*temp = 1
return *temp
}
}
*temp = 0
return *temp
}
func countString() {
sc.Scan()
s := strings.Split(sc.Text(), "")
N = len(s)
for i := range s {
switch s[i] {
case "A":
A++
case "B":
B++
case "C":
C++
}
}
}마무리
이 문제는 현재 시점으로 전날에 접했던 Dev Carnival의 3번 문제와 유사하다는 느낌을 받았습니다. 해당 문제는 풀지 못했지만, 이 문제를 통해서 간접적으로 풀이를 생각해볼 수 있을 것 같습니다. 또한 아직까지 완벽하게 이해하지 못한 부분이 있으므로, 해당 내용까지 이해한 후에 이 포스트를 최종 업데이트할 수 있도록 하겠습니다.
여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.
혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊
'PS > BOJ' 카테고리의 다른 글
| [BOJ/9372/Golang] 백준 9372 - 상근이의 여행 (0) | 2021.05.25 |
|---|---|
| [BOJ/12969/Golang] 백준 12969 - ABC (0) | 2021.05.24 |
| [BOJ/5582/Golang] 백준 5582 - 공통 부분 문자열 (0) | 2021.05.21 |
| [BOJ/2565/Golang] 백준 2565 - 전깃줄 (0) | 2021.05.20 |
| [BOJ/5557/Golang] 백준 5557 - 1학년 (0) | 2021.05.19 |