[백준 16208] 귀찮음

오답풀이

설계

원하는 쇠막대의 길이 [ 5, 4, 6, 2 ] 가 주어졌을 때, 첫번 째 자르는 경우의 수는

1) 5를 잘랐을 때

5 * (4 + 6 + 2) = 60

2) 2를 자랐을 때

(5 + 4+ 6) * 2 = 30

매 번 자를 때마다 작은 값을 곱하도록 설계하자. 즉, 양 끝단 중 작은 값을 곱하도록 설계하였음.

또한, 자른 막대기는 배제하기 위해 자를 때마다 ArrayList의 remove operation으로 해당 막대기를 삭제하였음.

public class Prob16208 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int numStick = Integer.parseInt(br.readLine());
		List<Integer> stick = new ArrayList<>();
		int answer = 0;
		
		st = new StringTokenizer(br.readLine());
		while(st.hasMoreTokens()) {
			stick.add(Integer.parseInt(st.nextToken()));
		}		
		
        // stick의 남은 원소가 하나남을 때까지 반복
		while( stick.size() != 1) {
        	// stick의 첫번째가 마지막보다 작을경우 첫번째를 곱하도록 설계
            	// ex) [2, 4, 5, 3] -> 2 * (4 + 5 + 3)
			if(stick.get(0) < stick.get(stick.size()-1)) {
				answer += stick.get(0) * remainSum(stick.subList(1, stick.size()));
				stick.remove(0);
			}
            	// stick의 마지막이 첫번째보다 작을 경우 마지먹을 곱하도록 설계
            	// ex) [6, 4, 5, 3] -> 3 * (6 + 4 + 5)
			else {
				answer += stick.get(stick.size()-1) * remainSum(stick.subList(0, stick.size()-1));
				stick.remove(stick.size()-1);
			}
		}
		System.out.println(answer);
		
	}

	private static int remainSum(List<Integer> stick) {
		int answer = 0;
		for (int i=0; i<stick.size(); i++) {
			answer += stick.get(i);
		}
		return answer;
	}
}

 

개선 풀이

문제점

1. 불필요한 remove operation으로 인한 시간초과

배제를 위해 remove 를 쓰지않고 인덱스를 적절히 조정하면 배제하면서 접근할 수 있을 것임

 

2. 설계 자체의 오류

사실, 어느 쪽을 자르던 자르기위한 최종비용은 같음.

X = 쇠막대기 전체의 길이

a1, a2, a3, a4 = 각 막대의 길이 라고 하자.

case1) 앞쪽이 계속 작은 값의 경우

비용 = a1 * (a2 + a3 + a4) + a2 * (a3 + a4) + a3 * (a4) + a3 * (0) = a1a2 + a1a3 + a1a4 + a2a3 + a2a4 + a3a4

 

case2) 뒷쪽이 계속 작은 값의 경우

비용 = (a1 + a2+ a3) * a4 + (a1 + a2) * a3 + (a1) * a2 + (0) * a1 = a1a2 + a1a3 + a1a4 + a2a3 + a2a4 + a3a4

 

즉,

1. 어느쪽을 자르던 자르기위한 최종비용은 동일함 

2. n개의 막대기를 서로 곱했다는 사실을 알 수 있다

 

코딩

식을 다시 정리하면 다음과 같다.

비용 = a1 * (X - a1) + a2 * (X - a1 - a2) + a3 * (X - a1 - a2 - a3) + a4 * (X- a1 - a2 - a3 - a4)

 

package greedyApproach;

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

public class Prob16208 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int numStick = Integer.parseInt(br.readLine());
		int[] plan = new int[numStick];
		long total = 0;
		long answer = 0;
		st = new StringTokenizer(br.readLine());
		for (int i=0; i<numStick; i++) {
			plan[i] = Integer.parseInt(st.nextToken());
			total += plan[i];
		}
		
		for (int i=0; i<numStick; i++) {
			total = total - plan[i];
			answer += plan[i] * total;
		}
		System.out.println(answer);
		
		
	}
}