이번 글에서는 프로그래밍 문제 사이트 백준 Online Judge의 문제들 중 Solved.ac 난이도 기준 Silver III에 해당하는 난이도의 문제들을 풀어보도록 하겠습니다.
풀어볼 문제들은 1463번 : 1로 만들기, 1003번 : 피보나치 함수, 9095번 : 1, 2, 3 더하기입니다.
1463번 : 1로 만들기
입력받은 수를 2 또는 3으로 나누거나 1을 빼는 과정을 반복해서 1까지 최대한 빨리 만드는 데 필요한 연산의 수를 출력하는 문제입니다.
매 연산마다 3가지의 선택지가 있기 때문에 일일이 탐색해서 경우의 수들을 따지는 것은 불가능합니다.
프로그램 제한 시간이 0.15초로 아주 짧은 것으로 보아 DP(동적 프로그래밍)를 이용하여 풀이해야 할 것으로 보입니다.
따라서 입력 범위에 해당하는 100만 크기의 배열을 선언해줍니다.
#include<stdio.h>
int arr[1000005];
int main() {
int N;
scanf("%d", &N);
arr[1] = 0;
for(int i=2; i<=N; i++) {
arr[i] = arr[i-1] + 1;
if(i%2 == 0 && arr[i] > arr[i/2] + 1) arr[i] = arr[i/2] + 1;
if(i%3 == 0 && arr[i] > arr[i/3] + 1) arr[i] = arr[i/3] + 1;
}
printf("%d", arr[N]);
}
풀이는 위와 같으며, 100만 크기의 배열을 main 함수 내에 선언하면 용량을 초과하기 때문에 전역 변수로 선언해주어야 합니다.
이후 연산 단계에서 2나 3으로 나눠지지 않는 경우에는 1을 빼는 선택지 밖에 없으므로 우선 1을 빼줍니다.
그 다음 2로 나누는 경우와 3으로 나누는 경우의 루트를 탈 때의 연산 횟수와 비교해서 더 적은 쪽을 기록해줍니다.
배열에 기록된 값은 이후 2의 배수나 3의 배수에서 다시 사용되므로 시간 소모 없이 빠르게 해결됩니다.
저의 경우 처음에 실수가 있었는데 2로 나누는 경우와 3으로 나누는 경우 else if를 사용하게 되면 i가 6의 배수일 때 어떤 것이 더 빠른지 모르기 때문에 반드시 둘 다 체크할 수 있도록 코드를 작성해주어야 합니다.
1003번 : 피보나치 함수
피보나치 함수가 있을 때, 이 함수에 N을 대입하여 호출할 경우 0과 1이 몇 번 출력되는지 계산하는 문제입니다.
이 경우 그냥 N이 증가함에 따라 0과 1이 몇 번 출력되는지 써보면서 규칙성을 찾으면 강제로 풀 수 있습니다.
그래서 문제에서 주어진 fibonacci 함수를 이용해서 테스트 하는 코드를 작성해보면 다음과 같습니다.
#include<stdio.h>
int zero, one;
int fibonacci(int n) {
if (n == 0) {
zero++;
return 0;
} else if (n == 1) {
one++;
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
int main() {
int T, N;
scanf("%d", &T);
for(int i=0; i<T; i++) {
scanf("%d", &N);
zero = 0, one = 0;
fibonacci(N);
printf("%d %d\n", zero, one);
}
}
이 코드를 토대로 프로그램을 실행시켜 규칙성을 찾아봅시다.
입력은 0부터 10개의 정수를 차례대로 입력해보도록 하겠습니다.
0은 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 순으로 횟수만큼 출력이 됩니다.
1은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 순으로 횟수만큼 출력이 됩니다.
규칙성을 찾아보면 N = 0, 1일 때를 제외하고 피보나치 수열대로 출력이 되며, 1은 0보다 하나 이전의 항만큼 출력됨을 알 수 있습니다.
따라서 그냥 피보나치 수열을 DP로 계산하고 위에서 발견한 규칙성대로 답만 출력해주면 됩니다.
#include<stdio.h>
int main() {
int fibo[100], T, N;
fibo[0] = 0, fibo[1] = 1;
for(int i=2; i<100; i++) fibo[i] = fibo[i-1] + fibo[i-2];
scanf("%d", &T);
for(int i=0; i<T; i++) {
scanf("%d", &N);
if(N == 0) printf("1 0\n");
else printf("%d %d\n", fibo[N-1], fibo[N]);
}
}
피보나치 수열을 DP(동적 프로그래밍)으로 배열을 이용해 계산해주는데 이 때 입력 범위가 N이 40 이하라고 했으므로 넉넉히 100까지 계산해줍니다.
이후 T를 입력받아 T의 수만큼 N을 입력받아 규칙대로 출력해주면 됩니다.
예외처리가 필요한 부분은 N = 0일 때뿐이므로 이 경우에만 1 0을 따로 출력해줍니다.
9095번 : 1, 2, 3 더하기
정수가 주어졌을 때 이 정수를 1, 2, 3으로 쪼갤 수 있는 경우의 수를 계산해서 출력하는 문제입니다.
1+2+1과 1+1+2를 다른 경우의 수로 세기 때문에 순서까지 고려해주어야 합니다.
#include<stdio.h>
int main() {
int dp[100] = {0, 1, 2, 4}, T, digit;
for(int i=4; i<=100; i++) dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
scanf("%d", &T);
for(int i=0; i<T; i++) {
scanf("%d", &digit);
printf("%d\n", dp[digit]);
}
}
우선 N = 1, 2, 3까지는 규칙상 3까지 사용될 수 있기 떄문에 직접 구해서 입력해두어야 합니다.
그 다음 N = 4부터 공식을 이용해볼 수 있는데, 다음의 3가지 방법이 있습니다.
( i ) N = 3에서 만든 배열에 1을 더해서 N = 4 만들기
( ii ) N = 2에서 만든 배열에 2를 더해서 N = 4 만들기
( iii ) N = 1에서 만든 배열에 3을 더해서 N = 4 만들기
케이스 ( i ), ( ii ), ( iii )은 각각 N = 3, N = 2, N = 1일 때의 경우의 수와 일대일 대응이 되므로,
dp[N] = dp[N-1] + dp[N-2] + dp[N-3]이라는 점화식을 구할 수 있습니다.
따라서 간단히 dp 배열 내에 값들을 미리 모두 구해준 뒤 입력받는대로 찾아서 출력만 해주면 됩니다.