728x90
언어_자바
이것이 코딩 테스트다_92p~95p 큰 수의 법칙
N: 배열의 크기
M: 숫자가 더해지는 횟수
K: 최대 가능한 연속성 횟수
입력 예시
5 8 3
2 4 5 4 6
public class _92BigNum {
static Integer n;
static Integer m;
static Integer k;
static Integer first, second;
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());
st = new StringTokenizer(br.readLine());
int[] number = new int[n];
for(int i =0; i < n; i++){
number[i] = Integer.parseInt(st.nextToken()); // 2 4 5 4 6 을 입력한다
}
Arrays.sort(number); // 2 4 4 5 6
first = number[n-1]; // 가장 큰 수(= 배열의 마지막 요소 )
second = number[n-2]; // 두 번째로 큰 수(= 배열의 마지막에서 앞 요소)
simpleSolution();
advancedSolution();
}
static void simpleSolution(){
System.out.println("[93p 단순하게 푸는 솔루션]");
int localM = m.intValue();
int result = 0;
while (true){
for(int i = 0; i <k; i++){
if(localM == 0) break; // m이 0이라면 반복문 탈출
result += first;
localM -= 1; // 더할 때마다 횟수 1씩 빼기
}
if(localM == 0) break;
result += second; // 두 번째로 큰 수는 한 번 더하기 (반복문 밖)
localM -= 1; // 더할 때마다 횟수 1씩 빼기
}
System.out.println("result : "+ result);
}
static void advancedSolution(){
System.out.println("[95p 최적화 솔루션]");
int count = (m / (k+1)) * k + m % (k+1); // 가장 큰 수가 더해지는 횟수 및 나머지가 생길 경우
int remain = m -count; // 나머지 횟수
int result = count * first + remain * second;
System.out.println("result : "+ result);
}
}
최적화 솔루션에 대한 설명을 하자면, 반복되는 수열을 활용한 풀이법이다.
위의 예시에서는 {6,6,6,5} 가 반복이 총 2회 되는 것을 알 수 있다. => {6,6,6,5} {6,6,6,5}
그렇다면 반복되는 수열의 길이는 4인 M을 (K+1)로 나눈 몫이 반복되는 횟수임을 알 수 있다.
여기서 중요한 점은 M이 (K+1)로 나누어 떨어지지 않는 경우도 고려해야한다.
즉, 가장 큰 수가 더해지는 횟수는 다음과 같은 공식이다.
int (M / ( K + 1 )) * K + M % (K+1)
(M/(K+1)) * K => 반복되는 횟수 * 최대 가능한 연속성 횟수
M % (K+1) => 나머지
라 볼 수 있다.
따라서 , count 는 가장 큰 수가 더해지는 수이므로 6이 나온다.
remain의 값은 2가 나온다. {6,6,6,5} {6,6,6,5}에서 가장 큰 수를 제외한 두 번째로 큰 수인 5의 총 횟수이다.
int result 의 식은 결국 풀어적자면, 6 * 6 + 2 * 5 = 46라고 할 수 있다.
<Reference>
728x90
'Algorithm' 카테고리의 다른 글
[프로그래머스] (181913) 문자열 여러 번 뒤집기 (0) | 2023.12.28 |
---|---|
[프로그래머스] (181921) 배열 만들기 2 (1) | 2023.12.26 |
[프로그래머스] (181925) 수 조작하기2 (0) | 2023.12.24 |
[프로그래머스] (181926) 수 조작하기1 (0) | 2023.12.24 |
[프로그래머스] (181927) 마지막 두 원소 (0) | 2023.12.24 |