문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog
문제 보러 가기
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- N개의 자연수 중에서 M개를 고른 수열
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.입력
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
4 4 2
예제 출력 1
2
4
예제 입력 2
4 2
9 7 9 1
예제 출력 2
1 7
1 9
7 9
9 9
예제 입력 3
4 4
1 1 2 2
예제 출력 3
1 1 2 2
백트래킹은 패턴화되어서 쭉쭉 잘푸는줄 알았는데 못풀었다....
테스트 케이스에 대해서 다 맞았는데 시간초과가 떴다.
틀린 코드
import sys
sys.stdin=open('input.txt','r')
def DFS(L,s):
store_value=0
if L==M:
print(*res)
else:
for i in range(s,N):
if visited[i]==0 and store_value!=nums[i]:
visited[i]=1
res[L]=nums[i]
store_value=nums[i]
# print('before: [i:{}번째, L:{},s:{},res:{}]'.format(i,L,s,res))
s+=1
DFS(L+1,s)
# print('after: [i:{}번째, L:{},s:{},res:{}]'.format(i,L,s,res))
visited[i]=0
if __name__=="__main__":
N,M=map(int,input().split())
nums=sorted(list(map(int, input().split())))
visited=[0]*N
res=[0]*M
DFS(0,0)
예제 2에 대해 주석 처리 한곳을 print 하면 다음과 같이 나온다.
i번째 for문에서 DFS를 수행하고 나면 아직 돌아온 i번째에서 s가 증가되어 있다.
예를 들어 before i=0일때 s는 0이고 이후 DFS를 수행을 다하고 after i=0이 되었을때 s는 1이 되어있다.
더보기
before: [i:0번째, L:0,s:0,res:[1, 0]]
before: [i:1번째, L:1,s:1,res:[1, 7]]
1 7
after: [i:1번째, L:1,s:2,res:[1, 7]]
before: [i:2번째, L:1,s:2,res:[1, 9]]
1 9
after: [i:2번째, L:1,s:3,res:[1, 9]]
after: [i:0번째, L:0,s:1,res:[1, 9]]
before: [i:1번째, L:0,s:1,res:[7, 9]]
before: [i:2번째, L:1,s:2,res:[7, 9]]
7 9
after: [i:2번째, L:1,s:3,res:[7, 9]]
after: [i:1번째, L:0,s:2,res:[7, 9]]
before: [i:2번째, L:0,s:2,res:[9, 9]]
before: [i:3번째, L:1,s:3,res:[9, 9]]
9 9
after: [i:3번째, L:1,s:4,res:[9, 9]]
after: [i:2번째, L:0,s:3,res:[9, 9]]
정답 코드
import sys
sys.stdin=open('input.txt','r')
def DFS(L,s):
store_value=0
if L==M:
print(*res)
else:
for i in range(s,N):
if visited[i]==0 and store_value!=nums[i]:
visited[i]=1
res[L]=nums[i]
store_value=nums[i]
# print('before: [i:{}번째, L:{},s:{},res:{}]'.format(i,L,s,res))
DFS(L+1,i+1) # 현재 i에서 다음 i로 넘어가야함
# print('after: [i:{}번째, L:{},s:{},res:{}]'.format(i,L,s,res))
visited[i]=0
if __name__=="__main__":
N,M=map(int,input().split())
nums=sorted(list(map(int, input().split())))
visited=[0]*N
res=[0]*M
DFS(0,0)
예제 2에 대해 주석 처리 한곳을 print 하면 다음과 같이 나온다.
반면 정답 코드는 before i=0일때 s=0이고 i=0일때 DFS를 다 돌고 다시 i=0일때 after에서 s=0 그대로 이다.
더보기
before: [i:0번째, L:0,s:0,res:[1, 0]]
before: [i:1번째, L:1,s:1,res:[1, 7]]
1 7
after: [i:1번째, L:1,s:1,res:[1, 7]]
before: [i:2번째, L:1,s:1,res:[1, 9]]
1 9
after: [i:2번째, L:1,s:1,res:[1, 9]]
after: [i:0번째, L:0,s:0,res:[1, 9]]
before: [i:1번째, L:0,s:0,res:[7, 9]]
before: [i:2번째, L:1,s:2,res:[7, 9]]
7 9
after: [i:2번째, L:1,s:2,res:[7, 9]]
after: [i:1번째, L:0,s:0,res:[7, 9]]
before: [i:2번째, L:0,s:0,res:[9, 9]]
before: [i:3번째, L:1,s:3,res:[9, 9]]
9 9
after: [i:3번째, L:1,s:3,res:[9, 9]]
after: [i:2번째, L:0,s:0,res:[9, 9]]
print 결과를 보며 차이점을 공부하자
비내림차순이라는 점을 구현하면 아래와 같이 코드를 작성할 수 있다.
from collections import deque
import sys
sys.stdin=open('input.txt', 'r')
def DFS(L):
store_value = 0
if L == M:
print(*res)
else:
if L==0:
s=0
else:
s=nums.index(res[L-1]) + 1
for i in range(s, N):
if not visited[i] and store_value != nums[i]:
visited[i] = True
res[L] = nums[i]
store_value = nums[i]
DFS(L+1)
visited[i] = False
if __name__=="__main__":
N, M = map(int, input().split())
nums = sorted(list(map(int, input().split())))
visited=[False]*N
res=[0]*M
DFS(0)
