이번 포스트에서는 프로그래밍 문제 사이트인 백준 Online Judge의 Solved.ac 기준 난이도 Silver IV에 해당하는 문제들인 1002번 터렛, 10773번 제로, 11653번 소인수분해를 풀이해보도록 하겠습니다.
1002번 : 터렛
문제를 상황에 맞게 각색해서 만들었기 때문에 이해하려면 시간이 조금 걸리지만, 요약하면 두 원의 중심 좌표와 반지름이 주어졌을 때 두 원의 교점의 수를 구하는 문제입니다.
두 중심 좌표의 거리와, 반지름의 합을 비교해주면 쉽게 해결이 가능해 보입니다.
#include<stdio.h>
int main() {
int T, x1, y1, r1, x2, y2, r2, disSquare, radiusDiffSquare, radiusSumSquare;
scanf("%d", &T);
for(int i=0; i<T; i++) {
scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2);
disSquare = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
radiusDiffSquare = (r1-r2)*(r1-r2);
radiusSumSquare = (r1+r2)*(r1+r2);
if(x1 == x2 && y1 == y2 && r1 == r2) printf("-1\n");
else if(radiusDiffSquare < disSquare && disSquare < radiusSumSquare) printf("2\n");
else if(radiusSumSquare == disSquare || radiusDiffSquare == disSquare) printf("1\n");
else if(disSquare > radiusSumSquare || disSquare < radiusDiffSquare) printf("0\n");
}
}
두 원의 중심과 반지름이 주어졌을 때 나올 수 있는 위치관계는 생각보다 많습니다.
가장 먼저 예외로써 고려해야 할 케이스는 두 원이 완전히 일치하는 케이스입니다.
이 경우에는 두 원이 완전히 겹쳐 교점이 무수히 많이 발생하므로 -1을 출력해주어야 합니다.
그 다음 교점이 2개 나오는 경우는 한 원의 중심이 다른 원 안에 있으면서 교차하는 경우와 원 밖에 있으면서 교차하는 경우가 있으므로 위와 같이 나누어 조건문을 작성해줍니다.
교점이 1개 나오는 경우는 두 원 사이의 거리가 두 원의 반지름의 합과 같은 경우입니다.
교점이 하나도 없는 경우도 역시 한 원의 중심이 다른 원 안에 있으면서 교차하지 않는 경우와 원 밖에 있으면서 교차하지 않는 경우로 나뉘므로 고려를 해주어야 합니다.
추가로 보통 math.h를 써서 루트를 계산하면 오차가 발생해서 정밀한 계산이 안되기 때문에 양변을 제곱해서 비교해주는 식으로 바꾸어 주는 것이 좋습니다.
10773번 : 제로
입력되는대로 숫자를 적어나가다가 0이 나올 때마다 마지막에 추가한 숫자를 지워서 더하는 방식의 문제입니다.
구조 자체는 스택을 구현해야할 것 같지만, 문제의 시간이 워낙 넉넉히 주어지기 때문에 배열을 사용해도 문제 없어보입니다.
다만 정수의 수는 최대 10만이고, 정수의 각 크기가 최대 100만까지 입력될 수 있으므로 마지막에 sum을 구할 때 long long int type을 사용해야 합니다.
#include<stdio.h>
int main() {
int N, arr[100005], digit, location = 0;
long long int sum = 0;
scanf("%d", &N);
for(int i=0; i<N; i++) {
scanf("%d", &digit);
if(digit == 0 && location != 0) arr[--location] = 0;
else if(digit != 0) arr[location++] = digit;
}
for(int i=0; i<location; i++) sum += arr[i];
printf("%d", sum);
}
풀이는 간단히 위와 같이 구현할 수 있습니다.
location은 현재 정수가 입력되는 위치를 말합니다.
0이 입력될 때마다 location의 정수를 지우고 location의 위치를 1 감소시켜줍니다.
11653번 : 소인수분해
아주 유명한 소인수분해 문제로, 말 그대로 정수가 입력되면 해당 수에 대한 소인수들을 모두 출력하는 문제입니다.
다만 문제의 조건이 약수가 여러 개여도 전부 출력해야하며 모두 오름차순으로 출력하는 것이 특징적입니다.
입력된 N이 1인 경우에는 아무것도 출력하지 않아도 되므로, 예외를 고려할 필요도 없습니다.
#include<stdio.h>
int main() {
int N;
scanf("%d", &N);
for(int i=2; i<=N; i++) {
while(N%i == 0) {
N /= i;
printf("%d\n", i);
}
}
}
코드는 아주 간단하게 작성이 가능한데, 소인수로 가능한 정수들을 2부터 시작해서 나눌 수 있을 때까지 계속 나눠주고 더 이상 나눌 수 없을 때 소인수를 증가시켜주면 됩니다.
i <= N까지 해도 처리 시간에 문제가 발생하지 않습니다.