[백준, 파이썬] 15657 N과 M(8)

https://www.acmicpc.net/problem/15657

15657번: N과 M (8)

이번 문제는 장장 1시간 가까이 삽질을 한 문제입니다.. 

알고리즘 자체는 dfs를 잘 알고 있다면 무난하게 풀 수 있는 문제입니다. 

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다

이 3가지 조건중에서 3번째 조건은 맨처음 받은 입력을 정렬만 해주면 해결되는 문제이고,

첫번째 M개를 고른다는 조건은 dfs에서 level M 까지 탐색하고 종료한다는 뜻 

두번 째 같은 수를 여러 번 골라도 된다 라는 조건은 알고리즘 적인 코딩을 통해 해결할 수 있습니다. 

그에 따라 작성한  코드는 다음과 같습니다. (주의!  틀린부분이 있습니다.)  

 

n,m = map(int, input().split(' ')) number = input().split(' ') number.sort() array = [] def dfs(level, index): if level == m: print(' '.join(result)) return for i in range(index,n): array.append(number[i]) dfs(leve+1, i) # 같은수를 여러번 뽑을 수 있으니까 i번을 넣음, # 여러번 뽑을 수 없다면 i+1을 넣음 array.pop(-1) #또다른 경우를 넣어주기위해 기존의 경우를 pop

위에서 틀린 부분 눈치채셨나요?

이 코드를 작성할 때 입력을 한자리수 숫자로 가정하고 작성하였습니다.. 

한자리 수일 때는 문제가 없지만 만약 숫자가 한자리수 이상일 경우에는 

문자열로 받을경우 1234 -> '1','2','3','4' 로 받게 되기 때문에 기존의 생각한 것과 다른결과를 얻게됩니다..

저는 이 부분을 생각을 못해 1시간 동안 오류를 찾는데 시간을 보냈습니다..

수정한 코드는 아래와 같습니다. 

 

n, m = map(int, input().split(' ')) number = list(map(int, input().split(' '))) number.sort() array = [] def dfs(level, index): if level == m: print(' '.join(map(str, array))) return for i in range(index, n): array.append(number[i]) dfs(level+1,i) array.pop() dfs(0,0)