백트래킹

https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 사용한 알고리즘 : 비트마스킹, 백트래킹 ※ 풀이 전략 1. 학생 개인이 풀 수 있는 문제를 2진수로 나타낸다. 풀 수 있는 문제는 1, 풀 수 없는 문제는 0으로 표기한다. ex) 예로 1번 학생이 총 5문제 중 2, 3, 5 번을 풀 수 있다고 한다면 10110 (2) = 22 이다.(오른쪽부터 1번 문제이고, 맨 왼쪽 비트가 5번 문제를 나타낸다.) 2. 백트래킹을 기법을 이용..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net import sys input=sys.stdin.readline n=int(input()) result=[0]*(50*20+1) #50이 20번 쓰여 더해진게 최대값이므로 RomaNum=[1,5,10,50] buf=[] cnt=0 def recur(x,start): if x==n: result[sum(buf)]=1 return for i in range(start,4): buf.append(RomaNum[i]) recur(x+1,i) buf.pop() recur(0,0) print(sum(re..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input=sys.stdin.readline N,M=map(int,input().split()) visited=[False]*(N+1) result=[] def back_Tracking(x): if x==M: print(' '.join(map(str,result))) return for i in range(1,N+1): result.append(i) back_Tracking(..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input = sys.stdin.readline N,M=map(int,input().split()) visited=[False]*(N+1) result=[] def recur(x): if x==M: print(' '.join(map(str,result))) return for i in range(1,N+1): if visited[i]==False and (len(result)..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import sys input=sys.stdin.readline n,m=map(int,input().split()) visited=[False]*(n+1) result=[] def recur(x): if x==m: print(' '.join(map(str,result))) return for i in range(1,n+1): if visited[i]==False: visited[i]=True r..