백트래킹 (2) 썸네일형 리스트형 [ BOJ / 파이썬 ] 1182.부분수열의 합 백트래킹의 n과 m이나 n queen 문제와는 살짝 차이가 있는 풀이 유형을 익힐 수 있었다. 보통 visited[n] = 1 func(n) visited[n] = 0 이런 식으로 방문여부를 방문append() - 재귀 깊이 + 1 - 방문pop() 요런 느낌이었는데. 이 문제에서는 func( 이 단계에서 실행 X, depth+1) func( 이 단계에서 실행 O, depth+1) 이런 식으로 풀어나갔다. ... 그리고 해당 문제 풀이에서는 정말 기초적인 수학 이해가 필요했다. 크기가 양수인 부분수열일 때만이라는 조건을 그냥 넘기려 했는데 예제 입력처럼 합이 0인 경우 = 그러니까 크기가 0인 경우는 예외처리를 할 필요가 있었던 것이다. 놓치기 쉬운 부분이었다. 풀이. 정답 import sys input.. [ BOJ / 파이썬 ] 15649. N과 M(1) 음 .. ? 의외로 꽤 빨리 풀리고.. 이전 문제 풀이보다 실행시간도 줄었다..! 음 .. 실력이 늘긴 늘었나 진짜. 코드. 통과. import sys input = sys.stdin.readline n, m = map(int, input().split()) visited = [0] * (n+1) result = [] def recur(k): if k == m: print(*result) return for i in range(1, n+1): if not visited[i]: visited[i] = 1 result.append(i) recur(k+1) visited[i] = 0 result.pop() recur(0) 처음에는 현재 방문한 배열(visited) 하나만 두고 k가 일정 깊이 도달했을 때 그냥.. 이전 1 다음
