본문 바로가기
반응형

알고리즘/백트래킹9

[백준][Python] 1182번 부분수열의 합 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 코드 n, s = map(int,input().split()) n_list = list(map(int,input().split())) cnt = 0 def dfs(num,sum): global cnt if num >= n: return sum += n_list[num] if sum == s: cnt += 1 dfs(num+1,sum) dfs(num+1,sum-n_list[num]) dfs(0,0) print(cnt) 설명 df.. 2022. 8. 3.
[백준][Python] 15652번 N과 M (4) 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 코드 n,m = map(int,input().split()) s = [] def dfs(num): if len(s) == m: print(*s) return for i in range(num,n+1): s.append(i) dfs(i) s.pop() dfs(1) 2022. 8. 1.
[백준][Python] 15651번 N과 M (3) 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 코드 n,m = map(int,input().split()) s = [] def dfs(): if len(s) == m: print(*s) return for i in range(1,n+1): s.append(i) dfs() s.pop() dfs() 설명 같은 수를 여러번 골라도 되기 때문에 원래 코드에서 중복을 방지하는 visit[]를 없앴다. 2022. 8. 1.
[백준][Python] 15650번 N과 M (2) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 코드 n, m = map(int,input().split()) s = [] visit = [False] * (n+1) def dfs(): if len(s) == m: print(*s) return for i in range(1,n+1): if visit[i] == False: if s: if s[-1] < i: visit[i] = True s.append(i) dfs() s.pop() visit[i] = False else: visit[i] = True s.ap.. 2022. 7. 29.
반응형

티스토리툴바