[구름톤 챌린지, Java] 8일차, 통증(그리드)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. 통증 수치를 감소하는 도구는 붕대, 알약, 진통제가 있습니다.

2. 통증을 감소하는 도구는 각각 1, 7, 14의 수치를 감소시킵니다.

3. 툥증 N이 주어질 때 최소의 약품을 사용해서 0으로 만드는 개수를 결과로 출력합니다.

4. 도구를 사용할 때 0보다 작아지면 해당 도구는 사용할 수 없습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 수치 감소가 큰 도구부터 사용하여 0이 될 때까지 탐색합니다.

 

3. 탐색을 통해 얻은 도구 사용 최소 개수를 결과로 출력합니다.

 

 

구현

 

해당 문제에서 도구에 수치 감소 값이 불균형한다면 DP를 사용하여 풀어야 했지만, 

 

1 → ×7 → 7 → ×2 → 14 

 

배수이기 때문에 통증 수치 감소가 가장 큰 값부터 최대한 사용하는 경우가 도구를 최소로 쓰는 경우가 됩니다.

 

 

그래서 통증 수치가 14이면

 

1 × 14 = 14개

 

7 × 2 = 2개

 

14 × 1 = 1개

 

표현이 되며, 14을 감소시키는 진통제를 사용하면 됩니다.

 

결과적으로, 통증 수치 감소가 높은 도구부터 최대한 사용하는 경우가 도구를 최소로 사용하는 경우입니다.

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 8

 

2. 수치 감소가 큰 도구부터 사용하여 0이 될 때까지 탐색합니다.

 

 

통증 : 8

 

진통제(14) 사용 불가!

 

통증 : 8

 

알약(7) 1개 사용 가능!

 

통증 : 1

 

밴드(1) 1개 사용 가능!

 

3. 탐색을 통해 얻은 도구 사용 최소 개수를 결과로 출력합니다.

 

진통제(0개) + 알약(1개) + 밴드(1개) = 2개

 

 

2을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• 진통제, 알약, 밴드순으로 최대로 사용하도록 탐색합니다.
• 탐색한 뒤 사용한 도구의 개수를 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.*;
class Main {
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //통증의 수치 입력값 저장
        int N = Integer.parseInt(br.readLine());
        int result = 0;
        //알약, 진통제 감소 수치 배열
        int[] div = {7, 14};
        //진통제, 알약 순서대로 최대 사용!
        for(int i=1;i>=0;i--){
            result += N / div[i];
            N %= div[i];
        }
        //남은 통증 밴드로 처리
        result += N;
        //사용한 도구의 개수 BufferedWriter 저장
        bw.write(String.valueOf(result));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}

 

---

느낀 점

 

문제를 보았을 때 배수라는 것을 확인하고 DP가 아닌 탐욕 알고리즘으로 풀 수 있다는 것을 파악했던 경험이 뿌듯하였습니다.