이코테 그리디 알고리즘 문제 중 하나인 큰 수의 법칙 문제이다.
자연수가 주어졌을 때, M번 더하여 가장 큰 수를 만드는 문제인데 연속해서 K번까지만 더할 수 있다는 조건이 있다.
가장 큰 수를 만들기 위해서는 첫 번째로 큰 수를 M번 더하면 되는데 연속해서 K번까지만 더할 수 있다는 조건이 있어서 두 번째로 큰 수를 1번 더하고 다시 첫 번째로 큰 수를 반복해서 더하면 된다.
먼저, 입력받은 자연수로 배열을 생성하여 오름차순 정렬한 후 첫 번째로 큰 수와 두 번째로 큰 수만 필요로 하기 때문에 변수에 저장하였다.
두 번째로, 더할 때마다 횟수를 증가시킬 cnt 변수와 최종 결과값을 저장할 result 변수를 초기화하였고 반복문을 돌면서 m을 1씩 감소시켰다.
이 때, cnt가 k와 같아지면 두 번째로 큰 수를 더해주었고 각 반복마다 m을 1씩 감소시켜 0이 되면 반복문을 빠져나오게 구현하였다.
풀이 시간을 30분으로 정해놓고 풀었다. 여러 가지 풀이 방법이 있을 수 있다고 생각했고 일단은 답을 구하는 데에 초점을 맞춰서 풀었다. 이후 다양한 풀이를 보며 이전 코드를 개선해보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 큰수의법칙 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 수의 개수
int m = Integer.parseInt(st.nextToken()); // 더하는 횟수
int k = Integer.parseInt(st.nextToken()); // 연속해서 더할 수 있는 횟수
int[] numArr = new int[n]; // n개의 자연수
st = new StringTokenizer(br.readLine());
for (int i = 0; i < numArr.length; i++) {
numArr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(numArr); // 오름차순 정렬
int firstMax = numArr[numArr.length - 1]; // 첫 번째로 큰 수
int secondMax = numArr[numArr.length - 2]; // 두 번쨰로 큰 수
int cnt = 0;
int result = 0;
while (true) {
result += firstMax; // 첫 번째로 큰 수 더하기
cnt++; // 더하는 횟수 카운트
m--; // 더할 때마다 m 감소
if (cnt == k) {
result += secondMax; // 두 번째로 큰 수는 한 번만 더해도 됨
cnt = 0;
m--;
}
if (m == 0) {
break; // m번만큼 더하면 종료
}
}
System.out.println(result);
}
}
분명 더 깔끔한 코드가 있을 것 같다는 생각이 들었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 큰수의법칙 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()); // 수의 개수
int m = Integer.parseInt(st.nextToken()); // 더하는 횟수
int k = Integer.parseInt(st.nextToken()); // 연속해서 더할 수 있는 횟수
int[] numArr = new int[n]; // n개의 자연수
st = new StringTokenizer(br.readLine());
for (int i = 0; i < numArr.length; i++) {
numArr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(numArr); // 오름차순 정렬
int firstMax = numArr[numArr.length - 1]; // 첫 번째로 큰 수
int secondMax = numArr[numArr.length - 2]; // 두 번쨰로 큰 수
int cnt = 0;
int result = 0;
for (int i = 0; i < m; i++) {
cnt++; // 더하는 횟수 카운트
if (cnt % k == 0) {
result += secondMax; // 두 번째로 큰 수는 한 번만 더해도 됨
} else {
result += firstMax; // 첫 번째로 큰 수 더하기
}
}
System.out.println(result);
}
}
두 번째 풀이의 if (cnt % k == 0)
이 부분을 보고 순간 짜릿했다. 나는 일차원적으로 if (cnt == k)
이렇게만 생각하고 cnt를 0으로 초기화해줬는데 cnt가 계속 증가하면서 k의 배수가 되면 두 번째로 큰 수를 더해주고 그렇지 않으면 첫 번째로 큰 수를 더해주면 되는 것이었다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 큰수의법칙 {
static int n, m, k;
static int[] numArr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 수의 개수
m = Integer.parseInt(st.nextToken()); // 더하는 횟수
k = Integer.parseInt(st.nextToken()); // 연속해서 더할 수 있는 횟수
numArr = new int[n]; // n개의 자연수
st = new StringTokenizer(br.readLine());
for (int i = 0; i < numArr.length; i++) {
numArr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(numArr); // 오름차순 정렬
int firstMax = numArr[numArr.length - 1]; // 첫 번째로 큰 수
int secondMax = numArr[numArr.length - 2]; // 두 번쨰로 큰 수
System.out.println(maxNum(firstMax, secondMax));
}
public static int maxNum(int firstMax, int secondMax) {
int cnt = 0;
int result = 0;
for (int i = 0; i < m; i++) {
cnt++; // 더하는 횟수 카운트
if (cnt % k == 0) { // cnt는 증가하여 k의 배수가 됨
result += secondMax; // 두 번째로 큰 수는 한 번만 더해도 됨
} else {
result += firstMax; // 첫 번째로 큰 수 더하기
}
}
return result;
}
}
마지막으로 큰 수의 법칙에 따라 답을 구하는 로직을 메소드로 분리하였다. 이전에는 main 메소드에 다 때려박았는데 앞으로는 최대한 기능별로 메소드를 분리해서 구현해보려 한다.