No, thank you

[문제]

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

그럼, 오늘도 역시 세준이는 0부터 9까지 모든 한 자리수가 자리수로 등장하면서, 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N이면서 0에서 9가 모두 등장하는 계단 수가 총 몇 개 있는 지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

[풀이]

필요한 입력데이터를 간추려 보면 현재 자릿수, 값, 그리고 각 자리수를 한번이라도 넣었는지 확인하는 변수가 필요합니다.

chairCount(location, value, state)는 해석하면 현재 자릿수에서 해당 값을 넣었을 때의 경우의 수에 대한 정보를 가지고 있습니다. 

주의 깊게 봐야할 점은 2가지가 있습니다.

1. long long 타입을 사용. 경우의 수가 상당히 크기 때문에 long long 타입을 사용하였고 출력서식형태는 %lld 입니다.

2. state는 해당 값을 이전에 넣었다면 true/false로 관리하기 위해 배열을 사용할 수 있지만 아래와 같이 비트마스크를 이용하여 관리할 수 있습니다. (state | 1<<value) 로 하여 value 자리에 1을 채워넣을 수 있습니다.

#include <stdio.h>

#include <string.h>

#define MOD 1000000000

int n;

long long cache[101][11][1<<11];

int chairCount(int location, int value, int state) {

if(value<0 || value>9) return 0;

if(location == n) {

if((state | (1<<value)) == (1<<10)-1) return 1;

else return 0;

}

long long & ret = cache[location][value][state];

if(ret!=-1) return ret;

state |= (1<<value);

return ret = (chairCount(location+1, value+1, state) + chairCount(location+1, value-1, state) ) % MOD;

}

int  main() {

scanf("%d", &n);

memset(cache, -1, sizeof(cache));

long long count = 0;

for(int i=1 ; i<=9 ; i++) {

count = (count + chairCount(1, i, 0)) % MOD;

}

printf("%lld", count);

return 0;

}

[더블릿] fac

N!의 끝에서 연속하는 0의 개수를 출력하는문제이다. 단, N! = N * (N-1) * (N-2) . . . * 3 * 2 * 1

예를들어 10! = 3628800 임으로 끝에서 연속하는0의 개수는 2이다.

입력

N이 주어진다. ( 1 <= N <= 1,000,000,000,000,000,000 )

출력

끝에서 연속하는 0의 개수를 출력한다. 단, 숫자가 너무커질수 있으므로 500,000,000,000,000,007로 나눈 나머지 값을 출력한다.

입출력 예

입력 

1

출력

0

입력

10

출력

2

입력

100

출력

24

입력

1422534662

출력

355633660

[풀이]

1! = 1

2! = 2

3! = 6

4! = 24

5! = 120    <--- 1개

6! = 720

7! = 5040

8! = 40320

9! =362880

10! = 3628800   <--- 2개

15! = 1307...000 <--- 3개

20! = 243...0000 <--- 4개

25! =1551..000000 <--- 6개

n!에서 n이 5로 나누어지면 0이 1씩 증가함을 알 수 있다.

n이 25이면 n/5 로 나누어져 5개의 0을 가지고, 추가적으로 25로 또 나누어지기 때문에 한개의 0을 가진다는 점근법을 세울 수 있다.

n이 50이면 50/5로 나누어져 10개의 0을, 추가적으로 50/25로 또 나누어지기 때문에 2개의 0을 가진다고 예측할 수 있다.

for (int i = 1; i <= 25; ++i) {

      cnt += (long long)(num / pow(5, i)) % 500000000000000007;

 }

[더블릿] 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;

}