[Python] 백준 16508 전공책

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

 

# 16508 전공책

words = input()
N = int(input())
cost = list()
title = list()
for _ in range(N):
    co, ti = input().split()
    cost.append(co)
    title.append(ti)

minimum = 1e9

for i in range(2 ** N):
    num = bin(i)[2:].zfill(N)
    temp_min = 0
    visited = [0] * len(words)
    for idx, nu in enumerate(num):
        # 탐색할 책이라면
        if nu == "1":
            temp_min += int(cost[idx])
            title_visited = [0] * len(title[idx])
            # 주어진 title 전체탐색
            for ti_idx, ti in enumerate(title[idx]):
                # 주어진 ANT 전체탐색
                for word_idx in range(len(words)):
                    # 방문한 곳이면 continue
                    if visited[word_idx] == 1 or title_visited[ti_idx] == 1:
                        continue
                    # title과 현재 단어가 같다면 방문처리
                    if words[word_idx] == ti:
                        visited[word_idx] = 1
                        title_visited[ti_idx] = 1
    if sum(visited) == len(words):
        minimum = min(temp_min, minimum)
if minimum == 1e9:
    minimum = -1
print(minimum)

 

N=4일 때, 0000, 0001, 0010, 0011의 꼴을 만들어, 1에 해당하는 idx의 전공책을 사용하여 글자를 만든다고 생각하면,

0000, 0001, 0010, 0011, 0100, ...의 숫자를 순서대로 반환하는 함수를 먼저 만들어야 했다.

 

처음엔 재귀함수를 이용하여 만드려 했으나, 이내 bit연산을 하는 것이 더 쉽겠다는 생각이 들어 그렇게 했다.

재귀함수는 위의 꼴보다, Combination과 Permutation을 구할 때 더 좋은 것 같다.

 

bit 연산을 표현하기 위해 bin, zfill을 사용했다.

 

아래 코드를 짜서 제출하였고, 11%에서 틀렸다는 안내를 받았다.

# 16508 전공책

words = input()
N = int(input())
cost = list()
title = list()
for _ in range(N):
    co, ti = input().split()
    cost.append(co)
    title.append(ti)

minimum = 1e9

for i in range(2 ** N):
    num = bin(i)[2:].zfill(N)
    temp_min = 0
    visited = [0] * len(words)
    for idx, nu in enumerate(num):
        # 탐색할 책이라면
        if nu == "1":
            temp_min += int(cost[idx])
            # 주어진 title 전체탐색
            for ti in title[idx]:
                # 주어진 ANT 전체탐색
                for word_idx in range(len(words)):
                    # 방문한 곳이면 continue
                    if visited[word_idx] == 1:
                        continue
                    # title과 현재 단어가 같다면 방문처리
                    if words[word_idx] == ti:
                        visited[word_idx] = 1

    if sum(visited) == len(words):
        minimum = min(temp_min, minimum)
if minimum == 1e9:
    minimum = -1
print(minimum)

디버깅을 하며 문제를 찾아본 결과, title에서 사용했던 알파벳을 재사용하는 문제점을 발견하였다. 반례는 다음과 같다.

 

AAA
3
25000 JAVA
10000 OOP
30000 BINARYCHECK

A 3개를 만들기 위해 JAVA, BINARYCHECK가 모두 필요함에도, title의 방문 체크를 해주지 않아 25000이란 return이 나온다.

 

AAA
3
25000 JAVA
10000 OOPA
30000 BINARYCHECK

내가 생각한 부분에서 에러가 나는 것이 맞는지 체크하기 위해 다음과 같은 예시도 만들어보았고, 10000이란 return을 얻은 뒤에, title도 visit 처리를 해줘야겠다는 생각을 했다.

 

코드를 수정한 뒤에 제출하였고, 91%에서 시간이 초과되었다는 안내를 받았다.

python3 대신 pypy3로 제출해 맞았다는 안내를 받았다.

 

어느 부분에서 틀렸는지, 혹시 백준에서 좋아하는 sys.stdin.readline을 쓰지 않아서 틀렸는지 알아보기 위해 다음과 같은 코드를 제출해보았다.

import sys

input = sys.stdin.readline

# 16508 전공책

words = input()
N = int(input())
cost = list()
title = list()
for _ in range(N):
    co, ti = input().split()
    cost.append(co)
    title.append(ti)

minimum = 1e9

for i in range(2 ** N):
    num = bin(i)[2:].zfill(N)
    temp_min = 0
    visited = [0] * len(words)
    for idx, nu in enumerate(num):
        # 탐색할 책이라면
        if nu == "1":
            temp_min += int(cost[idx])
            title_visited = [0] * len(title[idx])
            # 주어진 title 전체탐색
            for ti_idx, ti in enumerate(title[idx]):
                # 주어진 ANT 전체탐색
                for word_idx in range(len(words)):
                    # 방문한 곳이면 continue
                    if visited[word_idx] == 1 or title_visited[ti_idx] == 1:
                        continue
                    # title과 현재 단어가 같다면 방문처리
                    if words[word_idx] == ti:
                        visited[word_idx] = 1
                        title_visited[ti_idx] = 1
    if sum(visited) == len(words):
        minimum = min(temp_min, minimum)
if minimum == 1e9:
    minimum = -1
print(minimum)

위 코드는 7%쯤에서 틀렸다는 안내를 받았다.

예전의 경험과 다른 분들의 코드를 봤던 경험상, readline을 사용할 때 strip 처리를 잘 해줘야 한다는 기억을 깨닫고, strip 처리를 해보았다.

백준에서 그냥 input을 받을 때는 상관이 없었지만,

백준에서 readline을 사용하거나, swea의 일부 문제에서 입력 문장의 앞뒤에(주로 뒤쪽에) 공백이 있는 경우가 있었고, 이러한 경우 알고리즘이 옳음에도 불구하고 틀렸다는 안내를 받는 경우가 있었다. (특히 swea ㅂㄷㅂㄷ... 2시간동안 왜 틀렸는지 디버깅했는데 strip() 안붙여서 틀렸다는 것을 알았을 때의 그 기분은..)

 

import sys

input = sys.stdin.readline

# 16508 전공책

words = input().strip()
N = int(input().strip())
cost = list()
title = list()
for _ in range(N):
    co, ti = input().strip().split()
    cost.append(co)
    title.append(ti)

minimum = 1e9

for i in range(2 ** N):
    num = bin(i)[2:].zfill(N)
    temp_min = 0
    visited = [0] * len(words)
    for idx, nu in enumerate(num):
        # 탐색할 책이라면
        if nu == "1":
            temp_min += int(cost[idx])
            title_visited = [0] * len(title[idx])
            # 주어진 title 전체탐색
            for ti_idx, ti in enumerate(title[idx]):
                # 주어진 ANT 전체탐색
                for word_idx in range(len(words)):
                    # 방문한 곳이면 continue
                    if visited[word_idx] == 1 or title_visited[ti_idx] == 1:
                        continue
                    # title과 현재 단어가 같다면 방문처리
                    if words[word_idx] == ti:
                        visited[word_idx] = 1
                        title_visited[ti_idx] = 1
    if sum(visited) == len(words):
        minimum = min(temp_min, minimum)
if minimum == 1e9:
    minimum = -1
print(minimum)

input() 뒤에 .strip()을 붙여준 뒤 돌려보았다.

python3에서는 동일하게 91%에서 시간 초과 알림을 받았고, pypy3은 맞았다.

readline을 사용했을 때 724ms이 소요되어, 804ms가 소요된 python3보다 다소 빠르다는 것을 알 수 있었다.

 

따라서, readline을 사용하지 않은 것이 결정적인 시간 초과 요인은 아니었다. 약간 시간이 더 소요되기는 했지만, 전체 title과 words를 탐색하는 알고리즘이 더 문제였던 것 같다.

 

다른 분들의 코드를 아직 보지 않았지만, backtracking과 같은 최적화 기법을 사용하지 않은 것이 문제인 것 같다.

 

---

정답을 맞힌 분들 중 빠른 시간 내에 답을 맞히신 분의 코드를 보고, backtracking을 적용하였다.

코드는 다음과 같다. 주석을 포함해 세 줄 정도 추가되었다.

# 16508 전공책

words = input()
N = int(input())
cost = list()
title = list()
for _ in range(N):
    co, ti = input().split()
    cost.append(co)
    title.append(ti)

minimum = 1e9

for i in range(2 ** N):
    num = bin(i)[2:].zfill(N)
    temp_min = 0
    visited = [0] * len(words)
    for idx, nu in enumerate(num):
        # 탐색할 책이라면
        if nu == "1":
            temp_min += int(cost[idx])
            # backtracking
            if temp_min > minimum:
                continue
            title_visited = [0] * len(title[idx])
            # 주어진 title 전체탐색
            for ti_idx, ti in enumerate(title[idx]):
                # 주어진 ANT 전체탐색
                for word_idx in range(len(words)):
                    # 방문한 곳이면 continue
                    if visited[word_idx] == 1 or title_visited[ti_idx] == 1:
                        continue
                    # title과 현재 단어가 같다면 방문처리
                    if words[word_idx] == ti:
                        visited[word_idx] = 1
                        title_visited[ti_idx] = 1
    
    if sum(visited) == len(words):
        minimum = min(temp_min, minimum)
if minimum == 1e9:
    minimum = -1
print(minimum)

temp_min을 계산하던 중, 기존 최소치인 minimum보다 클 경우, backtracking을 한다.

 

다른 분의 코드를 보기 전엔, 아직 title을 확인하지 않은, 남아 있는 cost들을 다 더한 뒤에, 그 cost 값을 다 더해도 minimum보다 작을 경우에만 for문에 들어가는 방식으로 짜야 한다고 생각했다. 코드로 치면 sum(cost[idx:]) 값을 구한 뒤 비교해보는 방식이었을 것 같다.

위와 같이 생각하고, backtracking하기엔 너무 복잡하다고 생각했다.

그런데, temp_min을 minimum과 비교하는 아주 간단하면서도 명확한 backtracking 방법이 있었다. 미처 생각하지 못한 방법이었다.

 

모두 backtracking을 적용한 예시이다. 실행시간을 비교해보았다.

위에서부터 순서대로 readline + python3, pypy3, python3이다.

이 문제에서 readline 사용 여부는 시간에 큰 영향을 미치진 않은 것 같다.