[구름톤 챌린지] Day11 통증 (2)

구름LEVEL

전체 코드는 제일 아래에 있습니다!

 

===문제 설명===

구름-그라운드 게임에는 통증이라는 시스템이 있다.

아이템을 사용해 통증 수치를 0으로 유지하는 것이 중요하다.

게임 안에는 통증 수치를 감소시켜 주는 아이템이 2 종류가 있다. 각 아이템 사용 시 감소시켜 주는 통증 수치가 다르다.

각 아이템은 원하는 만믐 획득할 수 있다.

 

플레이어는 적과의 전투에서 피해를 입어 현재 N의 통증 수치를 가지고 있다.

플레이어가 통증 수치를 0으로 줄이기 위해 필요한 아이템의 최소 개수를 구해보자.

단, 사용했을 때 통증 수치가 0보다 작아지는 아이템은 사용할 수 없음에 유의하시오.

 

11

2 7

---

 T I P 

- 이전의 통증 문제처럼 그리디로 풀면 안 됩니다. 

그리디의 조건
1) 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2) 최적 부분 구조(Optimal Substructure): 최종 해결 방법은 부분 문제에 대한 최적의 해결 방법으로 구성된다.

위의 두 조건 중 2번 조건을 만족하지 않는 문제 이기 때문에 다른 방식으로 풀어야 합니다.

reason)
9
3 5
가 입력으로 주어질 때, 그리디로 푼다면 5 1개를 먼저 선택하고 3 1개를 선택해서 9를 만들 수 없다는 답이 나옵니다.
하지만 이 문제는 3을 3번 사용해서 답을 도출해야 하는 문제입니다.

 

- 저는 이 문제를 동적 계획법 (Dynamic Programming)을 사용하여 풀이하였습니다.

동적 계획법 (DP: Dynamic Programming)
: 이전에 구했던 답을 재활용하는 방식

ex) 피보나치 수열

long[] fibo = new long[N];
fibo[1]=1;

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

 

- 이 문제에서는 아이템이 2개만 주어지기 때문에 따로 dp 배열은 만들지 않고, 반복문으로만 구현하도록 하겠습니다.

---

🔖 풀이과정

1. for문을 사용해 a 아이템 사용 개수를 i로 하여 남은 pain과 사용한 아이템 수를 cnt에 저장해 줍니다.

여기에서 계산한 cnt와 now가 이전에 계산한 값으로 다음 단계에서 재활용됩니다.

for(int i=0;i<=pain/a;i++){
  int cnt = i; // 아이템 사용 개수
  int now = pain - a*i; //전체 통증에서 a 아이템을 사용해 줄인 통증을 빼줍니다.

 

2. a아이템을 i개 사용한 후, 남은 통증을 b아이템을 사용해 0으로 만들 수 있는 경우

a아이템과 b아이템을 사용한 개수를 cnt에 저장하고 이 값이 최솟값인지 answer와 비교해 줍니다.

if(now%b==0){//남은 통증이 b아이템을 사용해서 0이 되는 경우
    cnt+=now/b;//b아이템 사용개수도 cnt에 합쳐줍니다.
    
    //cnt가 최솟값인지 확인해줍니다.(answer가 초기화 상태라면 그냥 answer에 넣어줍니다.)
    if(answer==-1 || cnt<answer){
        answer=cnt;
    }
}

 

3. for문을 돌면서 a아이템 사용 개수에 따른 아이템 최소 개수를 구하고, 반환해 줍니다.

---

전체 코드

import java.io.*;
import java.util.*;
class Main {
 public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
    Scanner s = new Scanner(System.in);
		
    int pain = s.nextInt();//통증
    int a = s.nextInt();//아이템 a가 줄여주는 통증 수치
    int b = s.nextInt();//b가 줄여주는 통증 수치

    int answer=-1;//최소 아이템 사용 개수
    
    for(int i=0;i<=pain/a;i++){
      int cnt=i; //a 아이템 사용 개수
      int now = pain-a*i; //a아이템을 사용한 후의 통증

      //남은 통증을 b로 없앨 수 있는 경우에만 아이템 사용 개수 계산합니다.
      //남은 통증을 b로 없앨 수 없다면 -1을 반환해야 하기 때문에 넘어갑니다.
      if(now%b==0){
        cnt+=now/b; //b아이템까지 사용한 개수를 cnt에 더합니다.
        
        //answer이 초기화 상태이거나 이전의 아이템 사용 개수보다 적을 때 cnt로 바꿔줍니다.
        if(answer==-1 || cnt<answer) answer=cnt;
      }
    }

    System.out.println(answer);
  }
}