이번 포스트에서는 Baekjoon Online Judge의 Solved.ac 난이도 기준 Silver III에 해당하는 11399번 ATM, 11726번 2×n 타일링, 2606번 바이러스 문제를 풀이해보도록 하겠습니다.
11399번 : ATM
문제가 길지만 간단히 말해서 사람들이 최소 대기 시간으로 기다리게끔 배열했을 때 총 기다리는 시간의 합이 얼마인지 구하는 문제입니다.
간단히만 생각해보아도 시간이 짧게 걸리는 사람이 앞으로 가야 대기 시간의 합이 감소할 것입니다.
따라서 인출하는데 필요한 시간이 적은 사람부터 오름차순으로 배열한 뒤 그 합을 계산해주면 될 것입니다.
사람의 수가 최대 1000명뿐이므로 빠른 시간 정렬을 사용할 필요없이 O(n^2) 알고리즘을 사용하도록 하겠습니다.
#include<stdio.h>
int main() {
int P[1001], N, temp, sum = 0;
scanf("%d", &N);
for(int i=0; i<N; i++) scanf("%d", &P[i]);
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++)
if(P[i] > P[j]) {
temp = P[i];
P[i] = P[j];
P[j] = temp;
}
for(int i=0; i<N; i++) sum += P[i]*(N-i);
printf("%d", sum);
}
인출 시간을 오름차순으로 정렬한 이후 생각을 해보면, 예를 들어 5명의 사람이 있을 때 맨 앞사람이 인출하는 동안은 5명이 기다리게 됩니다.
따라서 P[0] * N + P[1] * (N-1) + P[2] * (N-2) + ... 순으로 더한 값이 기다리는 시간의 총합이 됩니다.
11726번 : 2×n 타일링
높이가 2이고 길이가 n인 직사각형을 1x2 타일로 채우는 방법의 수를 계산하는 문제입니다.
공간의 높이가 2로 제한되어있기 때문에 길이만 고려해주면 됩니다.
n이 증가함에 따라 방법의 수가 기하급수적으로 늘어날 것이기 때문에 일일이 계산한다면 시간이 많이 소요됨을 예상할 수 있습니다. (방법의 수를 10007로 나눈 수를 출력하라는 부분에서도 답이 매우 큼을 예상 가능함)
따라서 동적 프로그래밍(DP)을 이용하여 문제를 풀어보도록 하겠습니다.
#include<stdio.h>
int main() {
int n, arr[1005] = {0, 1, 2};
scanf("%d", &n);
for(int i=3; i<=n; i++) arr[i] = (arr[i-1] + arr[i-2])%10007;
printf("%d", arr[n]);
}
우선 n이 1000 이하로 입력되므로 배열은 1000의 크기 정도로만 잡아주고, n = 0, 1, 2일 때 값을 초기화 해줍니다.
이제 2 x i 크기 타일을 채우는 규칙에 대해 생각해보면, 2 x (i-1) 크기 세트에 세로로 타일 하나를 붙이는 방법 + 2 x (i-2) 크기 세트에 가로로 타일 두 개를 붙이는 방법과 일대일 대응되어 그 수가 같음을 알 수 있습니다.
따라서 arr[i] = arr[i-1] + arr[i-2]임을 알 수 있습니다.
그런데 n이 500 이상으로 커지게 되면 long long int로도 그 수를 표현할 수 없을 정도로 경우의 수가 많아집니다.
어차피 마지막 답에서 10007에 대한 나머지를 구하나 배열에 10007로 나눈 나머지를 저장해가면서 연산하나 그 나머지 값은 결국 같기 때문에, %10007 연산을 수행해가면서 배열에 저장하면 됩니다.
2606번 : 바이러스
문제에 대한 부연설명이 길어서 편집했는데, 결국 요약해보면 네트워크로 연결되어 있는 컴퓨터의 수를 출력하는 문제입니다.
연결 관계를 이용해서 탐색을 수행하는 문제임을 알 수 있습니다.
#include<stdio.h>
int n, connection[101][101], visit[101] = {0, }, count = 0;
void dfs(int x) {
for(int i=1; i<=n; i++)
if(connection[x][i] && !visit[i]) {
visit[i] = 1;
dfs(i);
count++;
}
}
int main() {
int m, x, y;
scanf("%d\n%d", &n, &m);
for(int i=0; i<m; i++) {
scanf("%d %d", &x, &y);
connection[x][y] = 1;
connection[y][x] = 1;
}
visit[1] = 1;
dfs(1);
printf("%d", count);
}
간단히 dfs를 구현하여 탐색을 수행할 수 있게 합니다.
dfs 함수를 설명하자면 재귀적으로 연결된 노드들을 방문할 수 있게끔 되어있고, visit 함수를 이용해 이미 방문한 노드는 방문하지 않도록 하여 무한루프에 빠지지 않게 합니다.
문제에서 주의할 점은 1번 컴퓨터를 "통해" 감염되는 컴퓨터의 수를 구하는 것이므로, 1번 컴퓨터는 count에서 제외해야 합니다.
따라서 visit 배열의 1번 값을 1으로 바꾸고 탐색을 시작해야 합니다.