인프런 커뮤니티 질문&답변

내꿈은프로틴부자님의 프로필 이미지

작성한 질문수

세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)

브루트 포스 알고리즘 [문제풀이] : BOJ 1182

브루트 포스 BOJ 1182번에 관한 질문이 있습니다!

해결된 질문

24.09.09 00:36 작성

·

27

·

수정됨

0

 

 풀이 1번 (기본)에서 대부분의 코드를 이해했습니다.

그런데

# 인덱스가 lev인 원소 선택 X

search(lev + 1)

에서 잘 이해가 되지 않습니다.

혹시 lev이 0일 경우인가요?

답변 1

0

알리 Ally님의 프로필 이미지
알리 Ally
지식공유자

2024. 09. 09. 20:22

안녕하세요. 내꿈은프로틴부자님!

풀이 1번의 기본 풀이의 기본 원리는 문제에서 주어진 리스트 각 원소를 선택하는 경우와 선택하지 않는 경우를 모두 체크하여 합이 S가 되는 경우를 카운트 하는 것입니다.

 

코드에서 주어진 리스트의 각 원소의 지점을 lev로 나타내고 있으며, search(lev) 메소드를 통해 lev 지점을 선택하는 경우와 선택하지 않는 경우를 각각 구현했고, 재귀적으로 다음 lev를 선택하도록 search(lev + 1)를 호출하고 있습니다.

lev 지점의 원소를 선택한 경우엔 choose 리스트에 담고, 다음 지점을 선택하기 위해 search(lev + 1)을 호출합니다. 이후 재귀가 모두 끝난 뒤 choose에 담긴 원소를 제거해줘야함으로 choose.pop()을 해주고 있습니다.

lev 지점의 원소를 선택하지 않은 경우엔 곧바로 다음 지점의 원소로 가기위해 search(lev + 1)만 해주고 있는 것입니다.

 

재귀적으로 짜여진 코드이기 때문에 직관적으로 이해가 어려울 수 있는 풀이 코드입니다.

다시 한 번 제 설명과 함께 쭉 이해해보시고, 그래도 이해가 안되시면 재질문 남겨주세요.

감사합니다. :)