[백준] 18185번 : 라면 사기

https://www.acmicpc.net/problem/18185

18185번: 라면 사기 (Small)

효율적으로 라면을 사는 방법을 구하는 문제입니다.

 

3
1 0 1

으로 들어 오게 될 경우 1,3번에서 3의 cost로 라면을 살 수 밖에 없어 6이 되게 됩니다.

 

5
1 1 1 0 2

으로 들어오게 될 경우 1,2,3에서 7의 cost로 살 수 있고, 5에서 3의 cost로 2번 살 수 있어 총 13의 cost를 사용하여 라면을 살 수 있습니다.

 

해당 입력만 보고 풀게 된다면 소스는 이렇게 됩니다.

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));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int answer = 0;
		for(int i = 0; i < n; i++) {
			if(i < n - 2 && arr[i] != 0 && arr[i + 1] != 0 && arr[i + 2] != 0) {
				int min = Math.min(arr[i], Math.min(arr[i + 1], arr[i + 2]));
				
				answer += min * 7;
				arr[i] -= min;
				arr[i + 1] -= min;
				arr[i + 2] -= min;
			}
			else if(i < n - 1 && arr[i] != 0 && arr[i + 1] != 0) {
				int min = Math.min(arr[i], arr[i + 1]);
				
				answer += min * 5;
				arr[i] -= min;
				arr[i + 1] -= min;
			}
			else if(arr[i] != 0) {
				answer += arr[i] * 3;
				arr[i] = 0;
			}
		}
		System.out.print(answer);
	}
}

 

당연하게도, 해당 소스는 틀렸습니다.

 

여기서 여러 히든 케이스들을 생각하다 보면 정답이 나오게 됩니다.

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

public class Main {
	static int[] arr;
	static int answer = 0;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine()) + 2;
		
		arr = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n - 2; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < n - 2; i++) {
			if(arr[i + 1] > arr[i + 2]) {				
				two(i, Math.min(arr[i], arr[i + 1] - arr[i + 2]));
				three(i, Math.min(arr[i], Math.min(arr[i + 1], arr[i + 2])));
				one(i, arr[i]);
			}
			else {
				three(i, Math.min(arr[i], Math.min(arr[i + 1], arr[i + 2])));
				two(i, Math.min(arr[i], arr[i + 1]));
				one(i, arr[i]);
			}
		}
		System.out.print(answer);
	}
	
	public static void one(int idx, int min) {
		arr[idx] -= min;
		answer += min * 3;
	}
	
	public static void two(int idx, int min) {
		arr[idx] -= min;
		arr[idx + 1] -= min;
		answer += min * 5;
	}
	
	public static void three(int idx, int min) {
		arr[idx] -= min;
		arr[idx + 1] -= min;
		arr[idx + 2] -= min;
		answer += min * 7;
	}
}