[자바] 백준 22864 - 피로도 (java)

 문제 : boj22864

---

 

필요 알고리즘 개념

• 그리디 알고리즘
  
  • 논리적으로 최선의 경우를 만드는 규칙을 정해 모든 경우에 적용시켜서 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  뭔가 곱셈, 나눗셈으로 풀 수 있을 것 처럼 생겼는데, 단 한번이라도 M을 넘기면 안되는걸 판단하기가 많이 어려울 것 같다. 24시간만 판단하면 되므로 총 24번 매번 확인하면 된다. 확인 방식은 간단한데, 매번 A만큼 피로도가 쌓여도 M을 넘지 않을 경우 무조건 일을 하고, 현재 일을 하면 M의 피로도를 넘긴다면 무조건 쉬면 된다. 상세한 풀이는 이하 코드에 작성해두었다.

for (int i = 0; i < 24; i++) {	// 24시간동안
    if (aSum+a <= m) {	// aSum이 현재 피로도이다. a를 더해도 m 이하라면
        sum += b;	// 무조건 일을 한다.
        aSum += a;	// 피로도는 a만큼 증가
    } else {	// 일을 하면 피로도가 m을 넘을 경우
        aSum -= c;	// 무조건 휴식한다.
        if (aSum < 0)	// 주의점으로 현재 피로도가 음수라면 0이 되어야 한다.
            aSum = 0;
    }
}

 

 

---

 

코드 : github

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

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int sum = 0;
        int aSum = 0;
        for (int i = 0; i < 24; i++) {
        	if (aSum+a <= m) {
        		sum += b;
        		aSum += a;
        	} else {
        		aSum -= c;
        		if (aSum < 0)
        			aSum = 0;
        	}
        }
        System.out.print(sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}