[BOJ] 6603 로또

💡문제 분석 요약

• {1,2, .. ,49}에서 6개의 수를 골라 로또를 만든다.
• 로또 전략 : k(k>6)개의 수를 골라 집합 S를 만든 다음 → 그 수만 가지고 번호를 선택하는 것이다.
  • k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])
• 집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구해라 ~
  • ⇒ 경로를 추적해서 알아야 하기 때문에 dfs 사용
• 오 ~ 입력 방법이 특이하군 !

입출력

• 입력
  7 1 2 3 4 5 6 7 # k(6<k<13), k개의 수(집합 S에 포함되는 수, 오름차순)
  8 1 2 3 5 8 13 21 34 # same
  0 # 입력의 마지막 줄에는 0이 하나가 주어짐 ~
• 출력
  1 2 3 4 5 6 # 각 테스트케이스마다 수를 고르는 모든 방법 출력(오름차순)
  1 2 3 4 5 7
  1 2 3 4 6 7
  1 2 3 5 6 7
  1 2 4 5 6 7
  1 3 4 5 6 7
  2 3 4 5 6 7
  
  # 테케 사이에는 빈 줄 하나 ~
  1 2 3 5 8 13
  1 2 3 5 8 21
  1 2 3 5 8 34
  1 2 3 5 13 21
  1 2 3 5 13 34
  1 2 3 5 21 34
  1 2 3 8 13 21
  1 2 3 8 13 34
  1 2 3 8 21 34
  1 2 3 13 21 34
  1 2 5 8 13 21
  1 2 5 8 13 34
  1 2 5 8 21 34
  1 2 5 13 21 34
  1 2 8 13 21 34
  1 3 5 8 13 21
  1 3 5 8 13 34
  1 3 5 8 21 34
  1 3 5 13 21 34
  1 3 8 13 21 34
  1 5 8 13 21 34
  2 3 5 8 13 21
  2 3 5 8 13 34
  2 3 5 8 21 34
  2 3 5 13 21 34
  2 3 8 13 21 34
  2 5 8 13 21 34
  3 5 8 13 21 34

6 < k < 13

시간제한 : 1초

💡알고리즘 설계

1. 입력값 받기
2. 테스트케이스 돌면서 로또 번호 수집(dfs 실행, 테케 사이 빈줄 세팅)
3. 결과 출력

💡코드

31120 KB / 44 ms

import sys
sys.setrecursionlimit(10**6)

# dfs - backtraking 방법
def dfs_backtracking(s, idx, ans):
    # 2. 목적지인가? 6개 로또 번호를 탐색함
    if len(ans)==6:
        print(*ans)
        return 
    
    # 3. 인접한 곳 돌기
    for i in range(idx+1, len(s)):
        # 4. 갈 수 있나?
        if s[i] not in ans:
            # 1. 체크인
            ans.append(s[i])
            # 5. 가자.
            dfs_backtracking(s,i,ans)
            ans.pop()

# dfs - 새로운 리스트 만드는 방법
def dfs_new_list(s,idx,ans):
    global result
    # 1. 체크인
    ans = ans+[s[idx]]

    # 2. 목적지인가?
    if len(ans)==6:
        form = ' '.join(map(str, ans))
        result.append(form)
        # print(*ans)
        return
    
    # 3. 인접한 곳 돌기
    for i in range(idx+1, len(s)):
        # 4. 갈 수 있나?
        if s[i] not in ans:
            # 5. 가자.
            dfs_new_list(s,i,ans)

# 숫자 조합을 만들어야 함 = 파고 드는 경로가 중요함 (dfs)
def solution():
    # 1. 입력 값 받기
    tc = []
    while True:
        line = sys.stdin.readline().strip()
        if line[0] == '0':
            break
        
        # 이걸 어떻게 저장하지?
            # line[0] : k개의 수
            # line[1:] : 집합 S

        # k = int(line[0])
        # s = list(map(int, line[1:].split()))

        parts = list(map(int, line.split()))
        k = parts[0]
        s = parts[1:]
        tc.append({'k':k, 's':s})
    
    # 2. 세팅
    result = []

    for i in range(len(tc)):
        k = tc[i]['k']
        s = tc[i]['s']
        
        # 새로운 리스트 방식
        for idx, num in enumerate(s):
            dfs_new_list(s,idx,[])
        
        # 백트래킹 방식
        # for idx_ in range(len(s)):
        #     dfs_backtracking(s,idx_,[s[idx_]])

        result.append("") # 빈줄 추가

    result.pop() # 빈줄 제거 

    print('\\n'.join(result))

if __name__ == "__main__":
    solution()

💡시간복잡도

O(k^2)

💡 틀린 이유

• 출력 방식을 틀림
• 조합을 만들어서 매번 저장하는 로직을 어떻게 작성할지 몰랐음

💡 틀린 부분 수정 or 다른 풀이

입력 받아오는 부분 2가지 풀이 방법

    while True:
        line = sys.stdin.readline().strip()
        if line[0] == '0':
            break
        
        # 이걸 어떻게 저장하지?
            # line[0] : k개의 수
            # line[1:] : 집합 S

        # 방법 1
        k = int(line[0])
        s = list(map(int, line[1:].split()))

				# 방법 2
        parts = list(map(int, line.split()))
        k = parts[0]
        s = parts[1:]
        
        # 여긴 공통
        tc.append({'k':k, 's':s})

💡 느낀점 or 기억할정보

• 새로운 리스트 만들기 vs 백트래킹
  • 새로운 리스트 만드는 방식
    • ans = ans + [s[idx]] 이렇게 새로운 리스트 만들어서 재귀 호출에 전달
    • 각 재귀 호출마다 메모리에 새로운 리스트를 생성하기 위해 복사 과정, 메모리 사용 과정이 발생한다.
  • def dfs_new_list(s,idx,ans): global result # 1. 체크인 : ans = ans+[s[idx]] # 2. 목적지인가? if len(ans)==6: form = ' '.join(map(str, ans)) result.append(form) return # 3. 인접한 곳 돌기 for i in range(idx+1, len(s)): # 4. 갈 수 있나? if s[i] not in ans: # 5. 가자. dfs_new_list(s,i,ans)
  • 백트래킹 방식
    • 리스트를 수정하는 방식이다.
      • ans 리스트에 append하고 → 재귀 호출 끝난 후 → ans에서 pop 하기
      • 주어진 리스트를 재사용 하는 방식이라, 새로운 리스트 만드는 것에 필요했던 메모리 할당/복사 비 용이 들지 않음.
    • e.g., ans.append(6) → dfs_backtraking(s,i,[1,2,3,4,5,6]) → len==6이 되어 return되었을 때 → ans.pop() 실행으로 ans = [1,2,3,4,5]가 되고 → for i in range(idx+1, len(s)): 문을 이어 돌면서 if 8 not in ans: ans.append(8) dfs_backtracking(s,i,[1,2,3,4,5,8]) 뭐 요런 식으로 되는거지 ~ you know ~~?
  • def dfs_backtracking(s, idx, ans): # 2. 목적지인가? 6개 로또 번호를 탐색함 if len(ans)==6: print(*ans) return # 3. 인접한 곳 돌기 for i in range(idx+1, len(s)): # 4. 갈 수 있나? if s[i] not in ans: # 1. 체크인 ans.append(s[i]) # 5. 가자. dfs_backtracking(s,i,ans) ans.pop()
  • 2개의 방식 비교
    • 메모리 사용 : 백트래킹 > 새로운 리스트 (새로운 리스트가 각 재귀마다 리스트를 새로 생성해서 중첩된 재귀가 많아질수록 오버헤드가 크게 증가함)
    • 실행 시간 : 백트래킹 > 새로운 리스트 (리스트를 생성하는데 걸리는 시간과, 메모리 복사로 인한 오버헤드가 새로운 리스트 방식에 존재한다)
    • BUT 이 문제에서는 메모리/시간이 똑같이 나옴 !
  • 결론적으로, 재귀적 조합 생성 문제에서는 백트래킹 방식이 더 쉽다.
• 출력 format, 입력 format 맞추기 어려웠다. 특히 출력 format에서 tc 하나 끝날 떄 마다 빈 줄을 추가하는 부분을 res = [] 이렇게 빈 출력 배열 만들고, tc 끝날 때 마다 res.append(””)로 처리했다. 그리고 마지막 tc 끝나고는 빈 줄이 있으면 안되니까 res.pop()했다.