구름톤 챌린지 3주 Day1

통증 (2) (Java)

제출한 답 :

import java.util.Scanner;

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

        int N = scanner.nextInt(); // 입력된 통증 수치
        int A = scanner.nextInt(); // 아이템 A의 감소량
        int B = scanner.nextInt(); // 아이템 B의 감소량

        int minItems = Items(N, A, B); // 최소 아이템 개수 계산

        System.out.println(minItems); // 결과 출력

        scanner.close();
    }

    public static int Items(int N, int A, int B) {
        // 통증 수치를 만들기 위한 최소 아이템 개수를 저장하는 배열
        int[] dp = new int[N + 1];

        // dp 배열 초기화
        for (int i = 1; i <= N; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        // 각 통증 수치에 대한 최소 아이템 개수 계산
        for (int i = 1; i <= N; i++) {
            if (i >= A && dp[i - A] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - A] + 1);
            }
            if (i >= B && dp[i - B] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - B] + 1);
            }
        }

        // N 통증 수치를 만들기 위한 최소 아이템 개수 반환
        return dp[N] == Integer.MAX_VALUE ? -1 : dp[N];
    }
}

블록은 못 받지만 그래도 날짜 무시하고 풀어보기!

이번주 안 했더니 금요일에 구름톤에서 포기하지말라고 문자 보내줌ㅋㅋㅋ

통증과 관련된 문제로 별 3개짜리...

피보나치수열... 언제 들어본 말인지..

동적계획법을 쉽게 설명해 준 블로그, 공부할 게 점점 쌓여간다.

Swift) 동적 계획법 (Dynamic Programming) 이해하기

안녕하세요:) 소들입니다 오랜만에 포스팅을 하는 것 같네요..! 아마 1월 달엔 자료구조 + 알고리즘에 대한 포스팅이 주일 것 같고.. 2월달부턴 다시 iOS + Swift에 대한 포스팅을 할 예정입니다 :) 오

babbab2.tistory.com

문제 풀이

필요한 개념

다이나믹 프로그래밍

분석

이전에 통증 문제를 탐욕 알고리즘으로 해결했습니다. 이 문제는 통증 문제에서 탐욕스럽게 풀리지 않는 문제입니다. 이전 문제와 달라진 것은 아이템이 2 종류이며, 서로 배수 관계가 아니면서 동시에 통증 수치가 0보다 작아지는 아이템은 사용할 수 없다고 합니다. 이 경우에 우리는 다이나믹 프로그래밍 즉, DP가 필요합니다.

문제 풀이

동적 프로그래밍으로 필요한 진통제의 개수가 최소인 경우를 찾아볼 겁니다. 그러기 위해서는 그리디 알고리즘이 통하지 않는 반례를 찾고, 최소인 경우를 찾기 위한 규칙을 어떻게 만들 수 있는지 고민하면 문제는 쉽게 해결할 수 있습니다.

그리디 알고리즘의 반례

N = 18, A = 2, B = 5 인 경우를 생각해 보겠습니다. 기존처럼 그리디 알고리즘을 사용해볼게요.

먼저 A < B 이므로, B 를 사용하여 N 을 최대한 나눕니다. 몫은 3이고, 나머지도 3이 나올 것입니다.

이제 나머지에 대해 A 를 사용해 나누겠습니다. 몫이 1이고, 나머지가 1입니다. 통증 수치가 남아버렸습니다.

문제의 조건에 따라 더이상 아이템을 사용할 수 없겠네요. 수치를 0으로 만들 수 없으니 -1 을 출력합니다.

하지만 손으로 계산해보면 B 2개, A 4개 를 사용해 18 을 만들 수 있으며, 이것이 최소 개수입니다.

그리디 알고리즘을 사용하면 위와 같이 예외 상황이 생깁니다. 따라서 그리디 알고리즘이 아닌 다른 방법으로 문제를 풀어야 합니다.

다이나믹 프로그래밍

동적 계획법 이라고도 합니다. 이론적으로 설명하면 이전에 구했던 답을 재활용하는 방식이라고 할 수 있습니다. 이를 설명할 때 자주 등장하는 예시는 피보나치 수열 입니다. 같이 살펴볼게요.

피보나치 수열은 처음 두개의 값이 0 과 1 이며, 이 다음 값은 맨 끝의 두 값을 더하여 만듭니다.

즉, 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 과 같이 진행되는 것입니다. 이를 재귀로 구현해보면 다음과 같습니다.

import java.io.*;
class Main {
		// 첫 두값을 종단점으로 잡아줍니다.
    public static void main(String[] args) {
        System.out.println(fibo(8));   // 21
        System.out.println(fibo(40));  // 102334155
    }
    public static long fibo(int N) {
        if (N == 0) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
		//N 번째 피보나치수는 N - 1번째, N - 2번째 피보나치수의 합이므로 재귀로 호출합니다.
        return fibo(N - 1) + fibo(N - 2);
    }
}

fibo(8) 에 비해서, fibo(40) 은 상대적으로 오랜 시간에 걸려서 출력이 됩니다. 이는 재귀 함수의 특성과 관련이 있습니다.

fibo(4)를 호출되면, fibo(4) 는 fibo(3), fibo(2) 를 각각 호출합니다.
fibo(4)가 호출한 fibo(3) 는 fibo(2), fibo(1) 을 호출 합니다. 이때, fibo(2) 가 중복됩니다.

이처럼, 중복으로 호출되는 함수가 N 이 커짐에 따라 빠르게 증가합니다. fibo(40) 을 호출할 때, fibo() 함수가 몇 번이나 호출되는지 확인해볼까요?

import java.io.*;
class Main {
		static long count = 0;
		public static void main(String[] args) {
        System.out.println(fibo(40) + " " + count);  // 102334155 331160281
    }
    public static long fibo(int N) {
				count++;
        if (N == 0) {
            return 0;
        }
        if (N == 1) {
            return 1;
        }
	  //N 번째 피보나치수는 N - 1번째, N - 2번째 피보나치수의 합이므로 재귀로 호출합니다.
        return fibo(N - 1) + fibo(N - 2);
    }
}

고작 40 번째 피보나치 수를 구하는 데에 fibo() 함수가 3억 3천만번 정도 호출됩니다. 이를 개선하기 위한 방법으로 동적 프로그래밍 고안되었습니다.

이번에는 생각을 뒤집어서, N 을 기준으로 0, 1 방향으로 내려가지 말고, 0, 1 에서 N 을 향해 올라간다면 재귀가 아니라 아래와 같이 해결할 수 있습니다.

import java.io.*;
class Main  {

    public static void main(String[] args) {
        int N = 40;
        long[] fibo = new long[N + 1];
        fibo[1] = 1;

        for (int i = 2; i <= N; i++) {
            fibo[i] = fibo[i - 1] + fibo[i - 2];
        }

        System.out.println(fibo[40]);  // 102334155
    }
}

방금 전에 사용한 재귀보다 훨씬 빠르게 40번째 피보나치 값을 구했습니다. 동적 계획법의 핵심은 이전에 구한 값을 저장해두고 다시 사용하는 것 입니다. 불필요한 중복 계산을 최대한 줄이는 방법인데, 이를 메모이제이션 이라고도 부릅니다.

규칙 만들기

이제 본격적으로 통증(2) 문제를 풀어봅시다. 다이나믹 프로그래밍의 핵심은 이전에 구한 값을 다시 사용하는 것 이라고 했습니다. 이를 문제에 적용해볼게요. 우선 아래와 같이 데이터 입력을 받은 뒤에 DP 변수를 활용합니다.

이때 DP 변수는 무한으로 초기화를 합니다. 최소 개수를 찾는 문제는 큰 수로 초기화를, 최대 개수를 찾는 문제는 작은 수로 초기화를 해야 합니다.

import java.util.Scanner;

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

        int N = scanner.nextInt();
        int A = scanner.nextInt();
        int B = scanner.nextInt();

        int[] DP = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            DP[i] = Integer.MAX_VALUE; // int 타입 배열을 최대값으로 초기화
        }
    }
}

다이나믹 프로그래밍 문제를 풀 때 중요한 것은, 선언한 DP 배열의 의미를 확실히 하는 것입니다. 저는 이 DP 배열의 의미를 다음과 같이 정의하겠습니다.

DP[i] 는, 통증 수치가 i 일 때, 통증 수치를 0으로 만들기 위해 필요한 아이템의 최소 개수이다.

이렇게 정의하면 DP[0] 은 0이 될 것입니다. 통증 수치가 0 이면 아이템을 사용하지 않아도 0이기 때문입니다.

# DP[0]의 값을 0으로 바꿉니다.
DP[0] = 0;

이 문제는 A 또는 B만큼 진통을 줄여주는 진통제를 여러 개 사용해서, N을 만드는 문제입니다.

만약에 현재 치료한 진통의 수치가 N-A면, 필요한 진통제는 하나 입니다. N-B면, 역시 필요한 진통제는 1개입니다. N이 아닌 어떤 i값이라고 해도 이 규칙은 동일합니다. 이 성질을 이용하면 아래와 같은 수식을 작성할 수 있습니다.

MAX_VALUE 가 나오는 이유는 자바의 MAX_VALUE의 값이 음수이기 때문입니다.

어떤 i 값에 대해서, i - A >= 0 이고 MAX_VALUE가 아닌 경우, DP[i] = DP[i - A] + 1 이다.
어떤 i 값에 대해서, i - B >= 0 이고 MAX_VALUE가 아닌 경우, DP[i] = DP[i - B] + 1 이다.

단, DP의 규칙을 지키기 위해서 아래와 같은 상황을 해결 할 코드도 필요합니다.

A의 값이 1이고, B의 값이 3 일때, dp[i-1] 의 값이 10이고, dp[i]의 값이 5라면 dp[i] = dp[i-1] + 1 로 갱신하는 것은 잘못된 갱신입니다. 이를 위해서, 우리는 갱신의 규칙으로 새롭게 진통제를 투여한 값이 기존의 DP 값보다 작을 때만 갱신하도록 수정할 수 있습니다.

조건에 부합하는 경우, DP[i] = Math.min(DP[i], DP[i - A] + 1) 이다.
조건에 부합하는 경우, DP[i] = Math.min(DP[i], DP[i - B] + 1) 이다.

이제 이렇게 그린 코드를 그대로 적용하면 됩니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
				..code
        dp[0] = 0;

        for (int i = 0; i <= N; i++) {
            if (i - A >= 0 && dp[i - A] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - A] + 1);
            }
            if (i - B >= 0 && dp[i - B] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - B] + 1);
            }
        }

    }
}

DP 배열의 모든 요소를 구했을 때, 주어지는 A, B 값으로 N을 만들 수 없는 경우가 있습니다. 그래서 만약에 DP[N] 의 값이 아직도 MAX_VALUE면, N을 만드는 것을 실패했기 때문에 -1 을 출력해야합니다.

하지만, MAX_VALUE가 아니라면 DP[N] 을 출력하면 됩니다. 이는 조건 연산자로 간단히 출력할 수 있습니다.

System.out.println(dp[N] != Integer.MAX_VALUE ? dp[N] : -1);

정답

import java.util.Scanner;

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

        int N = scanner.nextInt();
        int A = scanner.nextInt();
        int B = scanner.nextInt();

        int[] dp = new int[N + 1];

        for (int i = 0; i <= N; i++) {
            dp[i] = Integer.MAX_VALUE; // int 타입 배열을 최대값으로 초기화
        }

        dp[0] = 0;

        for (int i = 0; i <= N; i++) {
            if (i - A >= 0 && dp[i - A] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - A] + 1);
            }
            if (i - B >= 0 && dp[i - B] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - B] + 1);
            }
        }

        System.out.println(dp[N] != Integer.MAX_VALUE ? dp[N] : -1);
    }
}

저작자표시 비영리 변경금지

'문제풀기 > 구름톤 챌린지' 카테고리의 다른 글

구름톤 챌린지 3주 Day3 - 발전기(2) (2)	2023.09.02
구름톤 챌린지 3주 Day2 - 발전기 (0)	2023.09.02
구름톤 챌린지 2주 Day5 - GameJam (0)	2023.09.02
구름톤 챌린지 2주 Day4 - 폭탄 구현하기 (2) (0)	2023.08.25
구름톤 챌린지 2주 Day3 - 통증 (0)	2023.08.24

새롭게 공부시작하기

구름톤 챌린지 3주 Day1 - 통증 (2)

통증 (2) (Java)

제출한 답 :

문제 풀이

'문제풀기 > 구름톤 챌린지' 카테고리의 다른 글

티스토리툴바

구름톤 챌린지 3주 Day1 - 통증 (2)

통증 (2) (Java)

제출한 답 :

문제 풀이

'문제풀기 > 구름톤 챌린지' 카테고리의 다른 글

관련글

티스토리툴바