문제 탐색하기
입력 자료 정리
- N은 이후 입력으로 들어올 나무의 길이와 자라는 길이의 입력 개수이며,
또한 나무를 잘라서 구하기 위해 탐색해야하는 일자이다. - 이후 들어오는 입력은 각각 나무의 길이와 자라는 길이다
해결방법 추론
- 주어진 문제를 보았을 때, 나무를 잘라서 구할 수 있는 최대 양을 구하려면
결국, 자르는 날마다 최선의 선택을 하면 되는 것을 알 수 있다 - 최선의 선택을 하는 방법은 두가지 존재한다. 나무의 길이를 기준으로 하는 것과
자라는 길이를 기준으로 하는 것이다 - 나무의 길이를 선택했을 때를 한번 생각해보면,
나무의 길이만으로는 무언가 이어나가기 쉽지 않다. - 한가지 생각해볼 수 있는 방법은 시뮬레이션을 돌려가면서
현재에서 가장 길이가 큰 나무를 자르는 것인데,
일단 시간초과도 발생하고 최적의 선택이 되지 않는다. - 그렇다면 남은 방법은 나무가 자라는 길이를 기준으로 하는 것이다
- 나무가 자라는 길이를 기준으로 할 때, 또 두가지 선택지가 놓여진다
- 자라는 길이가 작은 것을 먼저 자를 것이가? 큰 것을 먼저 자를 것인가?
- 간단하게 선택할 수 있다 작은 것을 먼저 자르도록 오름차순 정렬해주면 된다
- 왜냐하면 일자가 지날 수록 자라는 크기는 점점 커진다.
큰 수를 곱할 수록, 더 많은 나무를 자를 수 있기 때문에 자라는 길이가 작은 것을 먼저 자르면
구할 수 있는 나무의 최대 양을 구할 수 있을 것이다.
시간복잡도 계산
- 이렇게 했을 때, 시간복잡도는 어떻게 될까? 정말 단순하게도 n만큼의 탐색만으로 끝난다.
- 오름차순 정렬 이후에 n만큼 순회를 돌면서 일자별로 자라는 길이에 곱한 다음,
현재 나무의 길이를 더해주면 끝난다. - 따라서 시간복잡도는 O(n)이 되고 시간제한 안에 해결할 수 있다!
코드 설계하기
입력값 상태 관리
- 먼저 n은 변수로 관리해준다. 이후 들어오는 길이를 보관해야하는데,
쌍을 이루어야하는 값이 한줄씩 따로 들어온다 - 따라서 먼저 들어오는 값을 임시 배열에 저장한 뒤,
이어서 오는 값과 함께 클래스로 쌍을 지어준 배열에 저장해서 관리한다
정렬 기준 설정
- 앞서 해결방법에서 생각한 것처럼 자라는 길이를 기준으로 오름차순 정렬을 한다
- 또한 자라는 길이는 모두 다르다고 했으므로
자라는 길이가 같은 경우 추가 정렬에 대한 고민은 필요 없다
그리디 식 설계
- n만큼 순회하면서 앞서 선언한 ans 정답 배열에 값을 저장한다.
- ans는 long타입으로 선언해준다.
나무의 길이와 n의 최대 입력값은 각각 10만이고,
자라는 길이는 1만이기 때문에 충분히 int형 타입의 범위를 벗어날 수 있기 때문이다 - 그리디 식은 자라는 길이에 현재 진행한 날짜의 수를 의미하는
현재 탐색 인덱스 i를 곱하고, 첫날 올라갔을 때의 나무의 길이를 더해준다. - 첫날 올라갔을 때는,
나무가 성장하지 않기 때문에 0이 곱해지도록 i+1이 아닌 i로 곱해주면 된다
출력 설계
- 완성한 ans를 출력하면 정답이 된다.
정답코드
(1회차 시도 성공!)
import java.io.*;
import java.util.*;
class Pair{
int height;
int growth;
public Pair(int height, int growth) {
this.height = height;
this.growth = growth;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
Pair[] pairs = new Pair[n];
for (int i = 0; i < n; i++) {
int tmp = Integer.parseInt(st.nextToken());
pairs[i] = new Pair(arr[i], tmp);
}
Arrays.sort(pairs, (o1, o2)->{
return o1.growth - o2.growth;
});
long ans = 0;
for (int i = 0; i < n; i++) {
ans += (long) (i) * pairs[i].growth + pairs[i].height;
}
bw.write(ans+"");
br.close();
bw.close();
}
}
문제 링크:
Software Developer