인프런 커뮤니티 질문&답변
작성한 질문수
[완전탐색 (재귀, 백트래킹) ] 백준 15650, 15649
해결된 질문
작성
·
294
·
수정됨
1
안녕하십니까 코딩센세!
늘 친절한 답변을 달아주심에 감사의 말씀 드립니다.
문제를 복습하다가 오늘은 도저히 진도가 나가지 않아서 힌트를 요청드리고자 이렇게 질문글을 남깁니다.
백준 15650을 풀려고 노력중에 있었습니다. 그런데 선생님의 코드를 적용해서 문제를 해결하려 했으나, 중복되는 수열을 거르는 것에서 어려움이 있습니다.
원래 백준 15649는 4 2로 N M의 입력이 주어진 경우 출력은 아래와 같아야 하는데요.
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
여기서 백준 15650은 4 2로 N M의 입력이 주어졌을 때,
1 2
1 3
1 4
2 3
2 4
3 4
이 둘의 차이를 구현하려고 2시간을 넘게 고민해봐도,
[1,1]
[2,1], [2,2]
[3,1], [3,2], [3,3]
[4,1], [4,2], [4,3], [4,4]
를 걸러내는 방법을 모르겠습니다.
선생님이 한 번 봐주시면서 피드백 좀 주시면 감사하겠습니다!
답변 2
0
0
안녕하세요, 인프런 AI 인턴입니다.
욕망의햄버거님, 백준 15650과 15649 문제에 대해 깊게 고민하시며 학습에 임하시는 모습에 박수를 보냅니다.
두 문제의 큰 차이점은 15649번 문제가 순열(Permutation)을 구하는 것이고, 15650번 문제는 조합(Combination)을 구하는 것입니다. 순열은 순서가 상관이 있지만, 조합은 순서를 고려하지 않습니다. 따라서, 백준 15650번에서 중복되는 수열을 거르기 위해서는 선택한 다음 숫자가 이전에 선택한 숫자보다 항상 커야 합니다.
재귀 함수를 사용하여 숫자를 선택할 때, 이전에 선택한 수보다 큰 수만 선택하는 조건을 추가해서 중복을 방지할 수 있습니다. 예를 들어, 다음과 같은 접근을 할 수 있습니다.
- 정수
start를 재귀 함수의 파라미터로 추가하고,start이후의 수부터 선택을 시작합니다.
start를 1로 초기화하고 첫 번째 수를 선택할 때는 1 이상의 수를 고릅니다.
- 다음 수를 선택할 때는 이전에 선택한 수
prev보다 뒤에 오는 수를 고르도록start를prev + 1로 설정합니다.
이러한 방식으로 조건을 추가하면, 중복을 피할 수 있고 오름차순으로 정렬된 수열을 얻을 수 있습니다.
막혔던 부분에 대한 이러한 접근 방식이 백준 15650 문제를 푸는 데 도움이 되었기를 바랍니다. 문제 해결 과정에서 추가적인 질문이 있으시면 언제든지 질문해주세요. 화이팅입니다!