등차수열합1 백준 16208 자바 - 귀찮음 (BOJ 16208 JAVA) 문제 : boj16208 1. 우선 그냥 풀어보자. 결국 현재 막대 크기를 x+y로 나눌 수 있을 때, 비용인 xy들의 합을 최소로 하고 싶은 것이다. 그렇다면 수학적으로 최대한 '작은수 x 큰수'가 되도록 하는것이 최소이다. '중간수 x 중간수'일수록 손해이다. 예를들어 현재 길이가 10일 경우 5x5는 25지만 1x9는 9다. 또한 맨 마지막 막대는 비용이 0이므로 (x+0 이므로 xy = 0) 결국 주어진 n개의 쇠막대를 길이가 짧은 순서대로 나누면 된다(그리디 알고리즘). 내 경우엔 어차피 a_i 0) { int cur = Integer.parseInt(st.nextToken()); cnt[cur]++; sum += cur; } long answer = 0; for (int i = 1; i 0) .. 2022. 2. 7. 이전 1 다음
