[Algorithm] ๐Ÿ•๏ธ๋ฐฑ์ค€ 4796 ์บ ํ•‘

0. ๋ฌธ์ œ

๋“ฑ์‚ฐ๊ฐ€ ๊น€๊ฐ•์‚ฐ์€ ๊ฐ€์กฑ๋“ค๊ณผ ํ•จ๊ป˜ ์บ ํ•‘์„ ๋– ๋‚ฌ๋‹ค. ํ•˜์ง€๋งŒ, ์บ ํ•‘์žฅ์—๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ฒฝ๊ณ ๋ฌธ์ด ์“ฐ์—ฌ ์žˆ์—ˆ๋‹ค.

์บ ํ•‘์žฅ์€ ์—ฐ์†ํ•˜๋Š” 20์ผ ์ค‘ 10์ผ๋™์•ˆ๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๊ฐ•์‚ฐ์ด๋Š” ์ด์ œ ๋ง‰ 28์ผ ํœด๊ฐ€๋ฅผ ์‹œ์ž‘ํ–ˆ๋‹ค. ์ด๋ฒˆ ํœด๊ฐ€ ๊ธฐ๊ฐ„ ๋™์•ˆ ๊ฐ•์‚ฐ์ด๋Š” ์บ ํ•‘์žฅ์„ ๋ฉฐ์น ๋™์•ˆ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์„๊นŒ?

๊ฐ•์‚ฐ์ด๋Š” ์กฐ๊ธˆ ๋” ์ผ๋ฐ˜ํ™”ํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ’€๋ ค๊ณ  ํ•œ๋‹ค.

์บ ํ•‘์žฅ์„ ์—ฐ์†ํ•˜๋Š” P์ผ ์ค‘, L์ผ๋™์•ˆ๋งŒ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ฐ•์‚ฐ์ด๋Š” ์ด์ œ ๋ง‰ V์ผ์งœ๋ฆฌ ํœด๊ฐ€๋ฅผ ์‹œ์ž‘ํ–ˆ๋‹ค. ๊ฐ•์‚ฐ์ด๊ฐ€ ์บ ํ•‘์žฅ์„ ์ตœ๋Œ€ ๋ฉฐ์น ๋™์•ˆ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์„๊นŒ? (1 < L < P < V)

์ž…๋ ฅ
์ž…๋ ฅ์€ ์—ฌ๋Ÿฌ ๊ฐœ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋Š” ํ•œ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , L, P, V๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ํฌํ•จํ•˜๊ณ  ์žˆ๋‹ค. ๋ชจ๋“  ์ž…๋ ฅ ์ •์ˆ˜๋Š” int๋ฒ”์œ„์ด๋‹ค. ๋งˆ์ง€๋ง‰ ์ค„์—๋Š” 0์ด 3๊ฐœ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ
๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด์„œ, ๊ฐ•์‚ฐ์ด๊ฐ€ ์บ ํ•‘์žฅ์„ ์ตœ๋Œ€ ๋ฉฐ์น ๋™์•ˆ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ์˜ˆ์ œ ์ถœ๋ ฅ์ฒ˜๋Ÿผ ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

1) ํœด๊ฐ€์ผ์ˆ˜๋ฅผ ์—ฐ์†ํ•˜๋Š” ์ผ์ˆ˜๋กœ ๋‚˜๋ˆˆ ๋ชซ, ๋‚˜๋จธ์ง€ ํ™œ์šฉ

2. ํ•ต์‹ฌ ํ’€์ด

1) ํœด๊ฐ€์ผ์ˆ˜๋ฅผ ์—ฐ์†ํ•˜๋Š” ์ผ์ˆ˜๋กœ ๋‚˜๋ˆˆ ๋ชซ, ๋‚˜๋จธ์ง€ ํ™œ์šฉ

int share = V / P;
	
rest = V % P;
sum += L * share;

if (rest <= L)
				sum += rest;
			else
				sum += L;

3. ์ฝ”๋“œ

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Greedy_10 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s[] = new String[3];
		int count = 1;
		
		while (true) {
			s = br.readLine().split(" ");

			int L = Integer.parseInt(s[0]);
			int P = Integer.parseInt(s[1]);
			int V = Integer.parseInt(s[2]);

			if(L == 0 && P == 0 && V == 0)
				break;
			
			int sum = 0, rest = 0;
			int share = V / P;
	
			sum += L * share;
			rest = V % P;

			if (rest <= L)
				sum += rest;
			else
				sum += L;
			
			System.out.println("Case "+count+": "+sum);
			count++;
		}
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณต~

๋„ˆ๋ฌด ์‰ฌ์›Œ์„œ ์˜คํžˆ๋ ค ์ž…์ถœ๋ ฅ์ด ๋” ์‹œ๊ฐ„์ด ์˜ค๋ž˜ ๊ฑธ๋ฆผ..

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ