출저 : https://www.acmicpc.net/problem/1182
풀기 전에 제가 사용한 템플릿 코드부터 소개할게요
private static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
private static String fastRead() throws Exception {
return bf.readLine();
}
private static ArrayList<Integer> getNumberList(String input) {
StringTokenizer st = new StringTokenizer(input, " ");
ArrayList<Integer> resultList = new ArrayList<>();
while(st.hasMoreTokens()) {
resultList.add(Integer.parseInt(st.nextToken()));
}
return resultList;
}제가 이번에 이 문제를 푸는데 사용한 언어는 Java 11버전 입니다. 따라서 Java에서 지원하는 기능을 이용하여 최대한 빠르게 입력 을 받도록 템플릿 코드를 마련할 필요가 있었습니다. 따라서 저는 BufferedReader를 이용해서 문자열을 입력받는 것으로 결정하였습니다.
그리고 getNumberList의 경우에는 fastRead 함수로 들어온 input을 StringTokenizer를 이용해서 문자열을 분리하여 Integer로 parsing한 다음에 ArrayList에 넣어서 ArrayList를 반환하는 기능을 수행합니다.
따라서 위의 두 메소드를 활용하면, 정수를 잘 입력받아서 저장을 할 수 있겠죠?
전략을 세워볼게요
일단, 현실 세계에서 저 문제를 어떻게 푸는지부터 생각을 해봐야해요.
현실에서 저 문제를 풀기 위해서는, 숫자를 중복 없이 선택하여 뽑아낸 다음에 뽑아낸 결과가 모두 더해서 조건을 만족하는지를 통해서 문제를 해결해요.
그러면 이거를 컴퓨팅적인 사고 로 옮겨줄 필요가 있습니다. 저는 다음의 기능을 생각했습니다 :
- 부분수열을 집어내야한다. 그러면 우리는 조합 을 골라내야하는데, 결국에는 하나 고르면 그 이후를 탐색하는 방식의 재귀함수 를 구현하면 되겠네!
- 재귀함수? 좋은데, 재귀함수의 진행 과정에서 계속 합을 해주고, 그걸 전달할 수단이 필요하다.
-> 합을 매개변수로 전달하는게 어때?
따라서 저는 위의 조건을 모두 만족할 수 있도록 다음의 코드 원형을 작성하기로 했습니다.
private static void partialSum(int k, int sequenceLength, int lastSelectedIndex, int sum) {
...
}파라미터에 대해서 설명을 해볼게요.
- int k : 현재 재귀함수가 숫자를 몇 개 까지 조합을 해냈는지를 전달하는 매개변수
- int sequenceLength : 결과적으로, 조합은 몇 개까지 허용을 하는가? (부분수열의 최대 길이)
- int lastSelectedIndex : 조합을 하는데 있어서, 마지막으로 집어낸 인덱스는 어디니? (인덱스를 초과한다는 뜻은, 조합에 실패했음을 의미하기 때문이에요!)
- int sum : 재귀함수가 돌아가면서, 집어낸 숫자들의 합이 얼마인지 전달하는 파라미터
다음 문단에서는, 재귀함수의 구현에 대해서 살펴볼게요.
어떻게 구현했어요?
일단 코드부터 볼까요?
// 현재 진행중인 상황, 부분수열의 원소 개수을 전달하여 조건 만족 시 count를 1씩 증가
private static void partialSum(int k, int sequenceLength, int lastSelectedIndex, int sum) {
// 탈출 조건
if(sum == objectSum && k == sequenceLength) {
count++;
return;
}
else if(lastSelectedIndex == N) // 인덱스 범위를 초과해서 탐색하려고 하는 경우
return;
// 점화식
for(int i = lastSelectedIndex; i < N; i++) {
partialSum(k + 1, sequenceLength, i + 1, sum + integerList.get(i));
}
}재귀함수의 기본 패턴은 "코드 초반에 탈출 조건을 명시해서, 조건을 만족하면 recursive를 멈추고, 다음 부분에는 점화식을 명시한다" 라는 방식을 채택합니다.
그러면 일단, 탈출 조건부터 분석할까요?
1. 탈출 조건
if(sum == objectSum && k == sequenceLength) {
count++;
return;
}
else if(lastSelectedIndex == N) // 인덱스 범위를 초과해서 탐색하려고 하는 경우
return;objectSum은, 우리가 원하는(결과가 원하는) 합을 저장한 변수입니다. 위의 탈출 조건에서는, 조합이 완료되었으며, 합도 원하는 합이 나왔을 때는 count를 증가시킨다. 그리고 종료시킨다. 그리고, lastSelectedIndex가 정해진 인덱스를 초과하는 경우에는(조합을 완성시키지 못하는 경우) 조합이 완성될 수 없으니 종료시킨다 라는 로직을 가집니다.
2. 점화식
for(int i = lastSelectedIndex; i < N; i++) {
partialSum(k + 1, sequenceLength, i + 1, sum + integerList.get(i));
}위에서 말했듯이, 현실세계에서는 조합을 하기 위해서, 숫자 하나를 고르면, 그 이후를 탐색해서 숫자를 골라낸다 라는 전략을 채택합니다. 이를 코드로 옮긴 것인데, k + 1을 통해서 재귀함수의 진행 현황을 전달하고, i + 1을 세번째 파라미터로 전달해서 마지막으로 골라낸 인덱스가 어디인지를 전달합니다.
그렇게 되면, 재귀함수는 매 번의 루프마다 lastSelectedIndex 부터 탐색을 시작하여 숫자를 고르기 시작하기 때문에, 조합을 잘 골라낼 수 있따! 가 되겠죠?
전체 코드는 소개만 하고 넘어갈게요
import java.util.*;
import java.io.*;
// 총 복잡도 : 2^N
public class PartialSum {
private static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
private static int N; // 정수 배열의 길이
private static int objectSum; // 목표 합
private static ArrayList<Integer> integerList; // 정수 배열
private static int count = 0;
public static void main(String[] args) throws Exception {
System.out.println("입력 시작");
// 조건 입력받기
ArrayList<Integer> conditionList = getNumberList(fastRead());
N = conditionList.get(0);
objectSum = conditionList.get(1); // 목표 합
// 부분 수열 입력받기
integerList = getNumberList(fastRead());
// 실행
for(int i = 1; i <= N; i++)
partialSum(0, i, 0, 0);
System.out.println(count);
}
private static String fastRead() throws Exception {
return bf.readLine();
}
private static ArrayList<Integer> getNumberList(String input) {
StringTokenizer st = new StringTokenizer(input, " ");
ArrayList<Integer> resultList = new ArrayList<>();
while(st.hasMoreTokens()) {
resultList.add(Integer.parseInt(st.nextToken()));
}
return resultList;
}
// 현재 진행중인 상황, 부분수열의 원소 개수을 전달하여 조건 만족 시 count를 1씩 증가
private static void partialSum(int k, int sequenceLength, int lastSelectedIndex, int sum) {
// 탈출 조건
if(sum == objectSum && k == sequenceLength) {
count++;
return;
}
else if(lastSelectedIndex == N) // 인덱스 범위를 초과해서 탐색하려고 하는 경우
return;
// 점화식
for(int i = lastSelectedIndex; i < N; i++) {
partialSum(k + 1, sequenceLength, i + 1, sum + integerList.get(i));
}
}
}그래도 설명할 부분은 설명하고 넘어갈게요. main 내부에서 반복문을 실행하는 모습을 확인할 수가 있는데, sequenceLength가 1부터 5가 될 수 있기 때문에, 이 부분까지는 재귀함수에서 구현하지 않고 외부로 빼냈답니다!
다음 문단에서는 저의 코드 복잡도를 분석하겠습니다.
시간 복잡도가 어떻게 돼요?
결론적으로, 제 코드의 복잡도는 2^N 의 복잡도를 가집니다. 왜 그렇게 되는지 설명을 드리겠습니다.
파스칼의 삼각형을 기억하시나요?
출처 : 위키백과
https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95
파스칼의 삼각형에서는 제일 n행에 위치한 수 들은 nCr 이라는 값을 가집니다.
그리고 n행에 위치한 수 들의 합은 0부터 n까지의 r에 대해서 nCr의 summation이기 때문에, 2^N이라는 값을 가집니다. (이는 Mathematical Induction을 통해서 증명이 가능합니다) 수학과 티내지마
제 코드의 경우에는 1부터 N 까지의 r에 대해서 nCr들의 summation이 코드의 시간 복잡도가 되기 때문에, 엄밀하게 따지면 2^N - 1이 정확한 복잡도로 계산이 되지만, Big-O Notation에 따르면 2^N으로 표기가 가능하답니다! 사실 빅오의 정의에 의해서 그렇게 된다는건 안비밀
다음에도 재밌는 문제로 돌아오겠습니다. 감사합니다!
