[java 백준] 실버 5/ 16208번 귀찮음

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        n = Integer.parseInt(br.readLine());
 
        long total = 0;
        long[] arr = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());// 입력 받은거 split해
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            total += arr[i];
        }
 
        long price = 0;
        for (int i = 0; i < n; i++) {
 
            long temp = total - arr[i];
            total -= arr[i];
            price += temp * arr[i];
 
        }
 
        System.out.println(price);
 
    }
 
}

 

문제를 풀면서 중요한 부분 + 내가 놓치고 있던 것 

---

1. 중요한 부분

어떻게 자르는지가 중요한게 아니라 하나하나씩 쳐내는게 중요하다 ! (어차피 비용은 같기 때문!)

 

2-1. 내가 놓쳤던거 

 

예제 1번을 예로 들자면, 

(3,5) , (4,2) 로  나누면 8,6이 되므로 8*6=48 이 되고 (3,5)는 3*5=15가 되고, (4,2)는 4*2=8 이 되서 다 더하면 71이된다.

하지만 이 문제에서는 이게 중요한게 아니다. 

 

우선 전체 길이인 14에서 (문제에서 길이를 다 더한 값을 언급함!)

먼저 3을 빼면,(11,3) 으로 나뉜다. 그러면 3*11=33이고 남은 길이는 11이된다. 

다음 5를 빼면 (5,6)으로 나뉜다. 그러면 5*6=30이 되고, 남은 길이는 6이다

다음 4를 빼면 (4,2)으로 나뉜다. 그러면 4*2=8 이되고, 남은 길이는 2이다.

2에서 2를 빼면 0이되므로 끝

 

어차피 하나씩 쳐내면 결국 값은 같다.

 

2-2. 내가 놓쳤던거 (2)

 

total, price같은 변수와 배열 arr의 자료형을 long으로 선언했어야 했다. 문제에서 n이 500,000보다 작거나 같은데, 이 경우 쇠막대를 15개만 만들어도 int 범위인 -2147483648 ~ 2147483647을 훌쩍 넘어가게 된다. 

long으로 자료형을 설정해주지 않으면 서브태스크 2,3번은 모두 틀리게 된다. 

 

비슷한 문제

---

 

16208은 그리디 알고리즘인 것 같은데 비슷한 문제로 설탕 배달이 있다. 

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

2839번: 설탕 배달

 

 

이건 파이썬으로 풀었었다.

 

 

x=int(input())
cnt_1=x//5
cnt_2=x%5
while True:
    if cnt_2%3!=0:
        cnt_1=cnt_1-1
        cnt_2=cnt_2+5
        if cnt_1<0:
            print(-1)
            break
 
    else:
        cnt_2=cnt_2//3
        print(cnt_1 + cnt_2)
        break

얘도 cnt_2가 3으로 나눠지지 않으면 cnt_1에서 5키로 뱉고, 5키로 만큼 cnt_2에 옮겨준다.

문제에서 언급했듯이 정확하게 배달하는게 중요하기 때문에 예를 들어 9키로를 배달한다면, 5키로 1개 3키로 2개 보단 3키로 3개가 더 낫다.