[코드트리 챌린지](7주차) conditional/특정조건에 맞게 k개중 1개를 n번 뽑기

문제:

자꾸 실력진단에서 이 문제를 틀려서 공부했다.

문제링크: https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition-under-constraint?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

풀이과정: 첨에 같은 수가 3번이상 나오면 안된다는 걸로 보고 실수 했다.. 근데 알고보니 연속해서 3번 나오는 것이었다. 그런데도 조건같은 걸 빼먹고 더해주는걸 빼먹고 해서 좀 헤맸다.

 

코드:

k, n = map(int, input().split())
num = []

def choose(curr, cnt):
    if curr == n+1:
        for a in num: print(a, end=' ')
        print()
        return
    for i in range(1, k+1):
        if cnt < 2 or num[-1] != i:
            prev_cnt = cnt
            if curr != 1  and num[-1] == i: cnt += 1
            else: 
                prev_cnt = cnt
                cnt = 1
            num.append(i)
            choose(curr+1, cnt)
            num.pop()
            cnt = prev_cnt
    return

choose(1, 0)

 

---

실력진단:

오늘 공부한 부분과 dfs는 맞았는데 dp문제에서 dfs로 풀려고 하다보니 틀렸다. 다음엔 dp문제를 풀어보겟다.