[JAVA] 백준 1173번

문제: https://www.acmicpc.net/problem/1173

1173번: 운동

운동 1173번 - 시뮬레이션

 

문제 재정의:

 

1분마다 운동/휴식 하나 선택해야 함

운동 N분 함

운동- T증가, 휴식 - R감소

맥박 M 넘기면 안 됨, m은 넘어야 함. 처음 맥박은 m

운동 과정 끝내는데 걸리는 시간의 최솟값 출력

 

---

 

생각한 것:

설탕 배분 문제(2839번)가 떠오름. 문제 개념이 비슷하다고 생각 듦

-이문제는 dp문제였음. dp로 접근하는 것이 맞는지.

근데 이건, t와 r이 제멋대로 주어지고 시간 최솟값 구하는 거라 시뮬레이션으로(흐름대로) 풀기로 함.

• 어떤 조합을 통해 최솟값 구할 것인지
  운동 N 분을 빨리 채워야 되니까 맥박 되면 무조건 운동하게 구현
  [운동을 일단 시작 - 맥박 넘길 것 같으면 휴식 - 운동할 수 있으면 맥박 되면 - 다시 운동]
• 잠재적으로 운동을 못하면 휴식을 해야 한다는 점
  
  
• 맥박 범위에 있는지 계속 검사
  
  
• 운동 횟수가 n에 도달했는지
  
  
  

---

 

시간 초과 난 코드:

 

~~생략
           int live_m= m; //현재 맥박. 최소 맥박으로 초기화
           int answer=0;//총 몇분 걸리는지 = 답
           int count=1; //운동 시간 추적

           while(count<=N){

               if(check(live_m, T, R, M, m)==false){
                   live_m-=R;
                   if(live_m<m) live_m=m; //최소 맥박보다 낮아지면 m이 되게
                   answer++;
                   //System.out.println("현재 맥박: "+live_m);
               }
               else if(check(live_m, T, R, M, m)==true){
                   live_m+=T;
                   count++;
                   answer++;
                   //System.out.println("현재 맥박: "+live_m);
               }
           }
           System.out.println(answer);
    }

    public static boolean check(int x, int plus, int minus, int max, int min){ //운동할 수 있는지 
        if(x+plus>max){
            return false;
        }
        else{
        return true;
        }

    }
}

-> 운동을 완료할 수 없으면 -1 출력 이 조건을 빼먹음

 

• 운동을 완료할 수 없는 상황은 도대체 어떤 상황?

조건 고려해서 짠 코드 1)

 

입력값이 다 동일할 때 while문이 loop돔

 

//개무식한 방법 아니냐 
if(N==m && m==M && M==T && T==R){
                   answer=-1;
                   break;
               }

 

조건 고려해서 짠 코드 2)

 

• 위 1) 조건만으로는 해결 x. 이것보다 더 정확한 조건이 필요한 듯
   
  1. 현재 맥박에서 한 번도 더할 수 없고(최대 맥박 넘어도)
  2. 휴식을 한다고 해도 무조건 최소 맥박보다 작아지는 경우일 때 (1 때문에 자동 성립이긴 함)

 

= 제자리걸음이어서 아무것도 못하는 경우

 

if(live_m+T>M){
               answer=-1;

           }
       else{
           //while문~~~~~
       }

 

이렇게 짜니까 됨!

 

---

 

최종 코드:

 

package till;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine()); //공백 기준으로 나눔

          int N = Integer.parseInt(st.nextToken()); //운동 몇분
           int m = Integer.parseInt(st.nextToken()); //최소 맥박
           int M = Integer.parseInt(st.nextToken()); //최대 맥박
           int T = Integer.parseInt(st.nextToken()); //운동-증가 맥박
           int R = Integer.parseInt(st.nextToken()); //휴식-감소 맥박

           int live_m= m; //현재 맥박. 최소 맥박으로 초기화
           int answer=0;//총 몇분 걸리는지 = 답
           int count=1; //운동 시간 추적

           if(live_m+T>M){ //뭘 해도 제자리 걸음일수 밖에 없는 상황은 -1출력
               answer=-1;

           }

           else{

           while(count<=N){

               if(check(live_m, T, R, M, m)==false){
                   live_m-=R;
                   if(live_m<m) live_m=m; //최소 맥박보다 낮아지면 m이 되게
                   answer++;
                   //System.out.println("현재 맥박: "+live_m);
               }
               else if(check(live_m, T, R, M, m)==true){
                   live_m+=T;
                   count++;
                   answer++;
                   //System.out.println("현재 맥박: "+live_m);
               }
               }
           }

           System.out.println(answer);

    }

    public static boolean check(int x, int plus, int minus, int max, int min){ //운동할 수 있는지 
        if(x+plus>max){
            return false;
        }
        else{
        return true;
        }

    }
}

 

 

---

 

깨달은 것:

 

최소 맥박보다 낮아지면 m이 되게

운동을 완료할 수 없으면 -1 출력

이 두 조건을 생각하지 못함. 모든 조건을 잘 좀 보자!

-> 힌트 안 보고 예외 상황을 생각해낸 거 친찬해~

 

---

 

재귀 쓰는 연습 하자. 훨씬 코드 이해하기 쉽고 깔끔해짐

 

팀원 코드:

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class quiz_1173 {
    static int N, m, M, T, R;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); //분
        m = Integer.parseInt(st.nextToken()); //최저 맥박
        M = Integer.parseInt(st.nextToken()); //최대 맥박
        T = Integer.parseInt(st.nextToken()); //운동
        R = Integer.parseInt(st.nextToken()); //휴식

        if(M<T+m) System.out.println(-1);
        else exercise(0,0,m);

    }

    public static void exercise(int time, int e_num, int X) {
        if(e_num==N) {
          System.out.println(time);
        }else{
            //운동
            if(X+T<=M) {
                exercise(time+1, e_num+1, X+T);
            }else{
                //휴식 - 최저맥박보다 작아질 때 -> m
                if(X-R<m) exercise(time+1, e_num, m);
                //휴식
                else exercise(time+1, e_num, X-R);
            }
        }

    }
}