완전탐색) BOJ 2309 - 아홉난쟁이 about fastcampus

[ak2j38]

아래는 제가 작성한 소스입니다.

'''java

static void rec_func(int k, int start, int value){
    if(k == M+1){
        if(value == 100){
            Arrays.sort(selected);
            for(int height : selected)
                if(height != 0){
                    sb.append(height).append("\n");
                }
            System.out.println(sb);
            System.exit(0);
        }
    }else{
        for(int cand=start; cand<=N; cand++){
            selected[k] = heights[cand]; value += heights[cand];
            rec_func(k+1, cand+1, value);
            selected[k] = 0; value -= heights[cand];
        }
    }
}

static void input() throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    heights = new int[N+1];
    selected = new int [M+1];
    for(int i=1; i<=N; i++) heights[i] = Integer.parseInt(br.readLine());
}

'''

[rhs0266]

잘 푸셨네요! 9개 중 7개를 선택하는 완전 탐색 연습을 굉장히 잘 짜신 것 같습니다. 질문에 대한 대답을 드리자면..!

print 하는 성격의 코딩 테스트라면 상관없겠지만, 함수형 코딩 테스트의 경우는 return을 성공적으로 수행해야 하기 때문에 exit 을 하시면 안됩니다. 이 경우에는 정답을 전역 변수로 저장해주는 작업이 필요하겠죠? 저 같은 경우는 전역 변수로 정답을 이미 찾았는 지를 기록하는 편입니다. 예를 들면, boolean find_answer_flag = false 를 만들고 if (value==100){ ...; find_answer_flag = true; } 를 해주는 것이죠. 추가로 rec_func 최전방에다가 if (find_answer_flag) return; 을 추가해주는 편입니다.

첨언) 코드 리뷰를 사아아알짝 해드리자면 (이미 매우 잘 짜셨지만..?) rec_func 재귀 호출 부분에서 value 처리를 아래와 같이 할 수도 있습니다!

            selected[k] = heights[cand];
            rec_func(k+1, cand+1, value + heights[cand]);
            selected[k] = 0;

[ak2j38]

아하 전역변수로 선언하고 rec_func 제일 윗줄에서 제어하면 되는 방법이었군요..!
value처리도 말씀해주신대로 적용해보겠습니다.
감사합니다!