[SWEA] 5215. 햄버거 다이어트

문제

문제 링크로 바로가기

문제 단순화

• 칼로리를 넘으면 안된다
• 만들 수 있는 조합들 중에 점수 합이 최대인 것을 구한다

=> 인덱스 배열을 이용하여 조합을 만들어 조건을 만족하는 것을 확인

문제풀이

인덱스배열을 이용하여 조합 생성하기

사전순 조합 생성 방식

사전에서의 순서처럼 만들 수 있는 조합을 만드는 것이다.

[0] -> score[0]
[0, 1] -> score[0] + score[1]
[0, 2] -> score[0] + score[2]
[0, 3] -> score[0] + score[3]
// 생략...
[3, 4] -> socre[3] + score[4]
[0, 1, 2] -> score[0] + score[1] + score[2]

사전순으로 만들 수 있는 인덱스 조합들을 전부 만들어서 가능한 경우를 다 계산하는 것으로,
이를 이해하는 것도 다소 시간이 걸리며,
인덱스의 범위를 벗어나지 않도록 해야한다

우선 전체 코드부터 제시하겠다

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {

            int N = sc.nextInt(), L= sc.nextInt(); // 재료, 칼로리 수
            int[] score = new int[N];
            int[] cal = new int[N];

            // 입력
            for (int i = 0; i < N; i++) {
                score[i] = sc.nextInt();
                cal[i] = sc.nextInt();
            }

            int maxScore = 0;

            for (int n = 1; n <= N; n++) { // n: 인덱스 조합의 개수
                int[] indices = new int[n]; // 인덱스 배열
                for (int i = 0; i < n; i++) {
                    indices[i] = i; // 조합별로 인덱스 배열 생성
                }
                
                while (indices[0] <= N-n) {
                    int totalScore = 0, totalCal = 0; // 매번 초기화
                    
                    for (int i = 0; i < n; i++) {
                        totalScore += score[indices[i]];
                        totalCal += cal[indices[i]];
                    }

                    if (totalCal <= L) {
                        maxScore = Math.max(maxScore, totalScore);
                    }

                    int i = n -1;
                    while (i >= 0 && indices[i] == N - n + i) {
                        i--;
                    }

                    if (i < 0) { // 전체 while 종료 조건
                        break;
                    }
                    indices[i]++;
                    for (int j = i +1; j < n; j++) {
                        indices[j] = indices[j-1] +1;
                    }
                }
            }

            System.out.println("#" + tc + " " + maxScore);
        }
    }

코드 설명

흐름도 요약

[0,1,2] → 끝 증가 가능? yes → [0,1,3]
[0,1,3] → 끝 증가 가능? yes → [0,1,4]
[0,1,4] → 끝 증가 불가 → 왼쪽 증가 → [0,2,3]
...
[2,3,4] → 더 이상 증가할 자리 없음 → 종료

그래서 필요한 코드

int i = n -1; // 현재 가장 끝 인덱스
//..생략
indicies[i]++;

위와 같은 형식으로 마지막만 사전순처럼 더해서 새로운 배열을 만든다
가령 n=3으로 살펴보자
[0, 1, 2] -> [0, 1, 3] 이런 식으로 증가한 것이다

그러면 이렇게 늘리다가 어떻게 종료하냐?

while (i >= 0 && indices[i] == N - n + i) {
	i--;
}

if (i < 0) { // 전체 while 종료 조건
	break;
}

위의 중간에 생략으로 작성한 코드가 무한정으로 늘어나는 것을 방지하기 위한 코드이다
indicies[i] == N-n+i를 통해 최고 인덱스가 만약 더이상 올라갈 수 없는 조건이라면
i--를 통하여 i = n-1에서 i = n-2가 된다
즉, 인덱스의 배열을 한 칸 더 앞으로 이동한 것이다

예를 들어, N=5고 n =3이라고 해보자
[0, 1, 2] , ...... [0, 1, 4] 이러면 indicies[i] == N-n+i인 상황이다 (가능한 인덱스의 마지막)
그래서 이제 ++의 대상을 마지막이 아니라 두번째 요소로 변경하는 것이다

그러면 [0, 2, 4]가 될 것 같으나... 다음 코드를 거치게 된다

for (int j = i+1; j <n; j++) {
	indicies[j] = indicies[j-1] + 1;
}

이 코드를 통해서 현재의 인덱스 정렬을 변경한다

이제 다시 끝 인덱스에 대하여 indicies[i]++ 를 통하여
[0, 2, 4] 이렇게 변형된다

이런식으로 반복하면 n=3 즉, 3개로 만들 수 있는 인덱스 조합들이 전부 사전 순으로 생성이 된다.

단계	indices	설명
1	[0, 1, 2]	시작 조합
2	[0, 1, 3]	맨 끝(2) → 3
3	[0, 1, 4]	맨 끝(3) → 4
4	[0, 2, 3]	끝이 4라서 왼쪽 자리(1) → 2, 뒤는 3으로 채움
5	[0, 2, 4]	끝(3) → 4
6	[0, 3, 4]	왼쪽 자리(2) → 3, 뒤는 4
7	[1, 2, 3]	첫 자리(0) → 1, 뒤 연속 채움
8	[1, 2, 4]	끝(3) → 4
9	[1, 3, 4]	두 번째 자리(2) → 3, 뒤 4
10	[2, 3, 4]	첫 자리(1) → 2, 뒤 연속 채움
끝	break	더 이상 증가할 i 없음

회고

이런식으로 n=1, n=2, n=3, n=4 ,... n=N일 때까지 만들 수 있는 조합들을 만들고
주어진 조건(칼로리 제한) 하에 maxScore를 구하는 문제였다

시간복잡도 O(N⋅2^N)

일단 이해하고 난다면 다음과 같은 사전순 조합 생성 방식은 기억해두면 좋을 거 같다
단, 조합의 크기가 고정되어있을 때나 기억하기에 좋지
조합의 크기가 고정되어있지 않다면 다소 복잡하게 느껴지기 쉬워서 DFS를 공부해서 완전탐색쪽을 이해하는 게 더 나을 듯 싶다

for (int i = 0; i < n; i++) {
	indices[i] = i; // 조합별로 인덱스 배열 생성
}
                
while (indices[0] <= N-n) {
	int totalScore = 0, totalCal = 0; // 매번 초기화
                    
	for (int i = 0; i < n; i++) {
		totalScore += score[indices[i]];
		totalCal += cal[indices[i]];
	}
    
	int i = n -1;
	while (i >= 0 && indices[i] == N - n + i) { i--; }
	if (i < 0) break;
	indices[i]++;
	for (int j = i +1; j < n; j++) {
		indices[j] = indices[j-1] +1;
	}
}

DFS 이용하기

그래서 준비해봤습니다
DFS 잘은 모르지만
얼마나 최적화가 되는지 확인해봅시다

    static int[] score;           // 맛 점수
    static int[] cal;             // 칼로리
    static int maxScore;          // 최대 맛 점수

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt(); // 테스트 케이스 수

        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            L = sc.nextInt();

            score = new int[N];
            cal = new int[N];
            maxScore = 0;

            for (int i = 0; i < N; i++) {
                score[i] = sc.nextInt();
                cal[i] = sc.nextInt();
            }

            // 완전탐색 시작
            dfs(0, 0, 0);

            System.out.println("#" + tc + " " + maxScore);
        }
    }

    // idx번째 재료를 포함할지 말지를 결정
    public static void dfs(int idx, int sumScore, int sumCal) {
        // 칼로리가 초과되면 종료
        if (sumCal > L) return;

        // 마지막 재료까지 확인했으면 최대 점수 갱신
        if (idx == N) {
            maxScore = Math.max(maxScore, sumScore);
            return;
        }

        // 현재 재료 포함 O
        dfs(idx + 1, sumScore + score[idx], sumCal + cal[idx]);

        // 현재 재료 포함 X
        dfs(idx + 1, sumScore, sumCal);
    }

예제를 통해 dfs 깊이 탐색

1
5 1000
100 200
300 500
250 300
500 1000
400 400

이런식으로 모든 조합들을 dfs를 통하여 완전탐색할 수 있음