[백준/파이썬]15650 N과 M(2)

 

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

15650번: N과 M (2)

문제

잘 안 보이는데 저기 빨간색 부분만 보면 된다.

 

검은색으로 숫자에 x 된 부분은 기존 N과 M(1)에서 지웠던 부분이다.

이번 문제는 중복 되는 숫자도 모두 지워야 하므로 빨간색으로 동그라미 쳐둔 숫자들도 지워야 한다.

 

여기서 규칙성을 찾아보면 빨간색으로 동그라미 된 숫자들은 한 단계 얕은 숫자들보다 작은 숫자들이다. 이를 제거해 주는 코드를 N과 M(1)의 코드에 추가해 주면 문제 해결이 가능하다.

 

 

정답

def dfs(deepth, n, s) :
    if deepth == m :
        print(' '.join(s))

    else :
        for i in range(1, n+1, 1) :
            if not str(i) in s :
                if deepth >= 1 and int(s[-1]) < i :
                    s.append(str(i))
                    dfs(deepth+1, n, s)
                    s.pop()
                elif deepth == 0 :
                    s.append(str(i))
                    dfs(deepth+1, n, s)
                    s.pop()

    
n, m = map(int, input().split())
ans = []
dfs(0, n, ans)

deepth가 0일땐 그냥 추가하면 되고.

 

deepth가 1이상일때 현재 층의 값과 상위 층의 값을 비교해 현재 층의 값이 더 클 때만 실행시킨다.

 

---

솔직히 좋은 방법으로 풀었는지 잘 모르겠다. 더 효율적으로 짤 수 있을것 같은데 아직은 어렵다!!!!!!!!!!!