(Python)백준 코딩테스트 연습 - 기타콘서트(1497)

1. 문제

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

1497번: 기타콘서트

2. 풀이

import sys
input = sys.stdin.readline
from collections import deque
from copy import copy
            
# n : 기타 개수
# m : 곡 개수
n, m = map(int, input().split())

# nList : 기타 별 연주 가능한 곡 리스트
nList = []

# 반복문으로 연주가능 곡 입력
for i in range(n):
    playMusic = input().split()[1]
    nList.append(playMusic)

# allComList : 모든 경우 조합의 리스트
allComList = deque()

def combinationFunc(appendList:list, listLen:int, depth:int):
#     print("listLen :", listLen)
    global nList
    global allComList
    for k, v in enumerate(nList[depth:]):
#         print("k :", k, "v :", v)
        appendList.append(v)
#         print("appendList :", appendList)
        if listLen == len(appendList):
            allComList.append(copy(appendList))
        else:
            combinationFunc(appendList, listLen, depth + 1)
        depth += 1
        appendList.pop()
#     print()
for i in range(1, n + 1):
    combinationFunc(deque(), i, 0)

# comSummaryList : 모든 조합을 요약한 정보 리스트
comSummaryList = []
for i in allComList:
    tempStr = "N" * m
    for j in i:
        for k, v in enumerate(j):
            if v == "Y" and tempStr[k] == "N":
                tempStr = tempStr[:k] + "Y" + tempStr[k+1:]
    comSummaryList.append([tempStr.count("Y"), len(i)])
# 칠 수 있는 곡이 가장 많은 순, 기타 수가 가장 적은 순으로 정렬
comSummaryList.sort(key=lambda x : (-x[0], x[1]))

# minGuitarCnt : 가장 많은 곡을 칠 수 있는 기타의 수
minGuitarCnt = comSummaryList[0][1]

if comSummaryList[0][0] == 0:
    print(-1)
else:
    print(minGuitarCnt)

3. FeedBack

 - 이 문제는 일주일이 걸려서 풀었던 문제로 쉽지 않았던 문제였다.

 이 문제를 해결할 수 있었던 주요 포인트는 모든 조합을 확인하여 그 중 최적의 조합을 찾는 방식의 프로세스였다.

 재귀 개념을 알고 있었기 때문에 어떤 것을 만들어야할지는 알지만, 아직 미숙한 탓인지 머리에서 생각하는 것을 실제 코딩하는 것에서 시간이 걸렸던 것 같다.

 계속 반복하여 재귀 코딩에 익숙해지는 것도 필요할 것으로 보인다.