[더블릿] koi 수열/series

[더블릿] koi 수열/series 

우리는 양의 정수들이 나열된 수열 을 < a1 ,a2 , a3,..,an >을 구하는 다음과 같은 두 문제를 풀려고 한다.

수열의 길이는 < a1 ,a2 , a3,..,an >수열에 포함된 정수들의 개수 n 이라고 정의한다.

문제 A: 양의 정수 M 이 주어질 때, a1 + a2 + .. + an = M 을 만족하면서 a1 * a2 ...* an 의 값이 가장 크게 되는 수열 을 구하시오. 단, a1 * a2 * a3 .. * an 의 값이 가장 크게 되는 서로 다른 길이의 수열이 두 개 이상 존재할 경우, 수열의 길이 n 이 최대인 수열을 구한다.

문제 B: 양의 정수 M 이 주어질 때, a1 * a2 * ... * am = M 을 만족하면서 a1 + a2 + .. + am 의 값이 가장 작게 되는 수열 을 구하시오. 단, a1 + a2 + ... + am 의 값이 가장 작게 되는 서로 다른 길이의 수열이 두 개 이상 존재할 경우, 수열의 길이 m 이 최소인 수열을 구한다.

문제 A에서 구한 수열의 길이 n 과 문제 B에서 구한 수열의 길이 m 을 출력하는 프로그램을 작성하시오.

예를 들어, M = 6 이면, 문제 A에서 구한 수열은 < 3, 3 >이므로 이 수열의 길이는 2이고, 문제 B에서 구한 수열은 < 2, 3> 이므로 이 수열의 길이는 2이다.

입력

첫째 줄에 정수 M 이 주어진다. 1 <= M <= 1,000,000 이다.

출력

첫째 줄에 문제 A에서 구한 수열의 길이 n 과 문제 B에서 구한 수열의 길이 m 을 한 개의 빈칸을 사이에 두고 차례대로 출력한다.

입출력 예

입력

6

출력

2 2

<풀이 중>

문제 A

아직 제대로 이해가 안됬지만 3을 최대로 집어넣고 나머지를 2로 채우는 것이 최적이라고 한다..

증명을 위해 2^n 과 n^2을 비교하면

n : 1 -> 2 > 1 

n : 2 -> 4 = 4 

n : 3 -> 8 < 9             <-- 3이 2보다 효율이 좋다

n : 4 -> 16 = 16 

n : 5 -> 32 > 25 

그 다음으로, n이 4보다 크면 항상 2^n > n^2 라는 것을 알 수 있다.

---> 결국 N/3 올림값이 결과값이 된다.

경우수를 나눠 보면 

N = 3n의 경우 : 3*n -> 답은 n 

N = 3n+1의 경우 : 3*(n-1) + 2*2 -> 답은 n+1 

N = 3n+2의 경우 : 3*n + 2*1 -> 답은 n+1 

문제 B

소인수분해하면 합이 최소가 된다. 주의해야 할점은 '최단' 길이이므로 2*2=4 의 경우를 생각해줘야 한다.

예를 들어 12는 {2, 2, 3}과 {4, 3}의 선택지가 생기는데 최단 길이이므로 {4,3}의 길이인 2가 출력되야 한다.

이 이유는 2^n과 n^2가 같은 수가 유일하게(?) 2이기 때문이다. 이 경우만 예외로 처리해주면 올바른 출력값을 얻을 수 있다.

32같은 경우는 {2, 2, 2, 2, 2} 와 {4, 4, 2}가 될 수 있고 최단길이 이므로 3이 출력되야 한다.

소스

#include <stdio.h>

#pragma warning(disable:4996)

int n;

int num1;

int num2;

int main() {

int temp;

scanf("%d", &n);

//문제 A

if (n % 3 == 0) {

num1 = n/3;

}

else if (n % 3 == 1) {

num1 = n / 3 + 1;

}

else {

num1 = n / 3 + 1;

}

//문제 B

temp = n;

  

  // 2*2 = 4인 경우를 처리해주기 위해 먼저 4로 나누어줄 수 있는 만큼 나누어준다.

while (temp % 4 == 0) {

temp = temp / 4;

num2++;

}

for (int i = 2; i < n; i++) {

while (temp%i == 0) {

temp = temp / i;

num2++;

}

if (temp == 1)

break;

}

printf("%d %d", num1, num2);

return 0;

}