이번 포스트부터는 드디어 백준(Baekjoon Online Judge)의 solved.ac 판정 난이도 기준 Silver 난이도의 문제들을 해결해보도록 하겠습니다.
Bronze 난이도의 문제들은 문제를 해결하기 위한 핵심 아이디어의 난이도보다도 여러가지 예외 상황들을 고려하여 복잡한 계산들을 정확하게 구현하는 문제들로 귀찮게하는 요소가 많았다면, Silver 난이도의 문제들부터는 주어진 자료형의 범위와 제한된 시간만을 가지고 어떻게 해결할 수 있을지 고민을 더 해야하는 문제들이 있습니다.
따라서 프로그래밍 기법 측면에서도 배울 점이 Bronze 난이도의 문제들보다도 많은 것 같습니다.
1010번 : 다리 놓기
강 서쪽의 모든 지점들에서 강 동쪽에 있는 지점들 중 일부에 다리를 겹치지 않게 놓는다고 할 때, 얼마나 많은 가짓수의 경우가 있는지 출력하는 문제입니다.
눈에 띄는 점은 이 문제에 0.5초의 시간 제한이 있는 것으로 보아, 이 문제를 진짜로 Brute-force 알고리즘으로 해결하려고 시도하는 사람들이 있나봅니다.
이 문제는 어렵지 않게도, 자세히 보면 다리가 꼬이면 안된다는 조건이 있기 때문에 강 서쪽의 지점을 N개, 강 동쪽의 지점을 M개라고 하였을 때 mCn의 경우의 수가 나타나는 것을 알 수 있습니다.
따라서 문제에서 제시한 입력 범위 내에서 mCn을 계산하는 프로그램을 구현해주면 됩니다.
#include<stdio.h>
int main() {
int T, N, M, A;
long long int ans;
scanf("%d", &T);
for(int i=0; i<T; i++) {
ans = 1;
scanf("%d %d", &N, &M);
A = N > (M-N) ? N : (M-N);
for(int j=A+1; j<=M; j++) ans *= j;
for(int j=1; j<=(M-A); j++) ans /= j;
printf("%d\n", ans);
}
}
다만 이 문제에서 가장 핵심적으로 어려운 부분은 입력 범위가 최대 30인데 이 경우 30!은 long long int의 범위조차도 넘어가버린다는 사실입니다.
따라서 mCn을 m!/(m-n)!n!으로 계산하지 말고, m x (m-1) x ... x (m-n) / n! 또는 m x (m-1) x ... n / (m-n)!과 같은 방법으로 곱셈을 중간까지만 하고 나누어주는 방식으로 해주어야 합니다.
따라서 위의 코드를 봐도 알 수 있듯 for문에서 변수의 범위 설정에 주의해야 합니다.
1018번 : 체스판 다시 칠하기
주어진 색의 보드에서 8x8 크기의 체스판을 만들기 위해 최소로 칠하기만 하면 되는 8x8 부분을 찾고, 그 부분에서 몇 칸의 색을 바꾸어야 하는지 계산하여 출력하는 문제입니다.
이러한 문제의 경우 8x8의 보드가 들어갈 수 있는 자리를 모두 찾아 검사를 해주어야 하므로 4중 for문을 사용하는 것이 이상적이며, 이 때 각 for문의 범위를 정확하게 설정해주어야 하기 때문에 헷갈리기 쉬운 문제입니다.
#include<stdio.h>
int main() {
int N, M, A, B, count, isOdd, min = 64;
char board[51][51];
scanf("%d %d", &N, &M);
for(int i=0; i<N; i++) scanf("%s", board[i]);
for(int A=0; A<=N-8; A++) {
for(int B=0; B<=M-8; B++) {
isOdd = 0;
count = 0;
for(int i=A; i<A+8; i++) {
isOdd = !isOdd;
for(int j=B; j<B+8; j++) {
isOdd = !isOdd;
if(board[i][j] == 'W' && isOdd) count++;
if(board[i][j] == 'B' && !isOdd) count++;
}
}
if(count < min) min = count;
count = 0;
isOdd = 1;
for(int i=A; i<A+8; i++) {
isOdd = !isOdd;
for(int j=B; j<B+8; j++) {
isOdd = !isOdd;
if(board[i][j] == 'W' && isOdd) count++;
if(board[i][j] == 'B' && !isOdd) count++;
}
}
if(count < min) min = count;
}
}
printf("%d", min);
}
저의 경우에는 A, B라는 변수를 따로 선언하여 A는 8x8 보드의 1행, B는 8x8 보드의 1열 좌표를 가리키는 변수로 사용하였습니다.
따라서 A의 범위는 0부터 N-8 미만까지이고, B의 범위는 0부터 M-8 미만까지가 됩니다.
A와 B가 정해진 이후 안쪽의 이중 for문은 해당 8x8 보드에서 색을 최소 몇 칸 바꿔야 체스판으로 만들 수 있는지 검사를 해주어야 합니다.
이 때 체스판에는 검은색, 흰색, 검은색, 흰색, ...으로 반복되는 패턴과 반대로 흰색, 검은색, 흰색, 검은색, ...으로 반복되는 패턴의 2가지가 있기 때문에 2가지 모두에 대하여 검사를 해주어야 합니다.
따라서 저는 isOdd라는 변수를 사용하여 1, 0, 1, 0과 같은 방식으로 칸을 이동할 때마다 계속 변경해주며 검사를 하였습니다. (ex : isOdd = 1이고 W이거나 isOdd = 0이고 B인지 검사, 또는 isOdd = 0이고 W이거나 isOdd = 1이고 B인지 검사)
이 때 주의할 점은 체스판에서 한 행의 끝 칸의 색과 다음 행의 첫 칸의 색이 같으므로 행이 바뀔 때는 색이 바뀌면 안됩니다. (따라서 isOdd와 같은 변수를 사용할 때도 두 번 바꾸어주거나 바뀌지 않도록 해주어야 함)
한 번의 검사가 끝날 때마다 총 몇 칸을 바꾸어야 하는지 검사하여 최솟값과 비교하여 최솟값보다 작은 것이 있는지 찾아주고, 검사가 모든 좌표에 대하여 끝난 이후 count 값을 출력해주면 됩니다.
탐색 범위 설정과 조건 설정이 어려운 것이지, 예외적인 테스트케이스나 출력 문제에 대하여 어려운 부분이 없기 때문에 탐색만 제대로 해준다면 어려울 것이 없는 문제였습니다.
1037번 : 약수
어떤 수의 모든 진약수가 주어졌을 때, 이 약수들이 어떤 수의 약수인지 그 수를 출력하는 문제입니다.
문제만 보면 아주 쉽지만, 본래의 수를 찾기 위해서는 가장 큰 진약수와 가장 작은 진약수를 찾아 곱해주어야 하기 때문에 무작위의 순서로 입력되는 약수들을 정렬해주어야 합니다.
즉, 이 문제는 정렬 알고리즘을 사용하는 가장 기초적인 문제 중 하나이며, 정렬 알고리즘을 사용할 줄 알아야 합니다.
#include<stdio.h>
int main() {
int N, A[51] = {0, }, temp;
scanf("%d", &N);
for(int i=0; i<N; i++) scanf("%d", &A[i]);
for(int i=N-1; i>0; i--)
for(int j=0; j<i; j++)
if(A[j]>A[j+1]) {
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
printf("%lld", A[0]*A[N-1]);
}
저의 경우 가장 간단하다고 판단되는 bubble sort를 이용하여 정렬을 진행해주었습니다.
버블 정렬에서 주의할 점은 바깥쪽 loop의 범위를 설정할 때 N-1부터로 잡아주어야 합니다. (방향에 따라 바뀔수도 있으나 여기서 작성한 정렬 방향으로는 N-1)
정렬이 끝난 뒤 최댓값과 최솟값이 들어있는 양 끝칸의 수를 곱하여주면 답을 얻을 수 있습니다.
long long int 범위까지 나올지는 모르겠으나 저는 혹시 몰라서 %lld로 출력해주었습니다.