백준(Baekjoon Online Judge)의 Silver V 난이도의 1059번 : 좋은 구간, 1064번 : 평행사변형, 1094번 : 막대기를 풀이해보도록 하겠습니다.
1059번 : 좋은 구간
정수 집합 S에 대하여 n을 포함하고 정수 집합 S의 원소들을 포함하지 않는 정수 구간을 좋은 구간이라고 정의할 때, 주어진 테스트케이스에 대하여 좋은 구간의 갯수를 출력하는 문제입니다.
범위는 대체적으로 다 작은 양수이므로, 계산 또는 출력 과정에서 자료형의 범위를 벗어날 걱정은 하지 않아도 됩니다.
또한 일일이 탐색을 진행한다고 하더라도 범위가 굉장히 작으므로 구현만 한다면 시간 제한을 벗어날 일은 없습니다.
우선 좋은 구간에 대해 생각해보기 위해, 간단히 주어진 수 n을 기준으로 양 방향으로 가장 가까운 집합 S의 정수가 n-3, n+3이라고 가정해봅시다.
그러면 양 끝 범위를 왼쪽 끝은 n-2, n-1, n 중 하나로 잡을 수 있고, 오른쪽 끝은 n, n+1, n+2로 잡을 수 있으므로 3x3이 되며, 여기서 {n}과 같이 n만 포함되어 있는 구간은 좋은 구간의 정의에 어긋나므로 1가지를 빼주어야 합니다.
즉, n과 가장 가까운 양쪽 방향의 S의 원소를 찾고, 양쪽으로 선택할 수 있는 끝 범위 정수의 수를 세서 곱해준 뒤, 1을 빼주면 답이 나옵니다.
#include<stdio.h>
int main() {
int L, S[1001] = {0, }, n, temp;
scanf("%d", &L);
for(int i=1; i<=L; i++) scanf("%d", &S[i]);
scanf("%d", &n);
for(int i=L; i>0; i--)
for(int j=0; j<i; j++)
if(S[j] > S[j+1]) {
temp = S[j];
S[j] = S[j+1];
S[j+1] = temp;
}
for(int i=0; i<=L; i++) {
if(S[i] > n) {
printf("%d", (n-S[i-1])*(S[i]-n)-1);
return 0;
}
else if(S[i] == n) {
printf("0");
return 0;
}
}
}
위의 코드를 보면 알 수 있듯, 우선 S 집합의 원소들을 크기순으로 정렬해야 합니다.
저의 경우 오름차순으로 정렬을 진행해주었으며, S[i]를 이용해 n과 비교하다가 n보다 큰 S[i]가 나오는 지점에서 S[i-1], S[i] 사이에 n이 포함되어 있음을 알 수 있습니다.
따라서 총 경우의 수로 (n-S[i-1])*(S[i]-n)-1가지를 출력해주도록 하였습니다.
이 문제에는 2가지의 예외가 있는데, 첫 번째는 n이 S의 원소와 같은 경우이고, 두 번째는 n이 S[0]보다도 작은 경우입니다.
첫 번째 문제를 해결하기 위해서는 n이 S[i]인 경우의 조건문을 따로 만들어 이 경우 좋은 구간이 존재하지 않기 때문에 0을 출력해주어야 합니다.
두 번째 문제의 경우, 저의 경우에는 S[0]은 그냥 0이 들어가는 칸으로 만들어두고, S[1]부터 S 원소들을 정렬하여 나머지는 똑같이 진행하였습니다.
이렇게 될 경우 n이 S[1]보다 작더라도 S[0]에 0이 있기 때문에 다른 상황과 마찬가지로 풀이할 수 있습니다.
1064번 : 평행사변형
주어진 세 점을 가지고 만들 수 있는 여러 평행사변형 중에, 둘레의 길이가 가장 긴 것에서 가장 짧은 것을 뺀 값을 오차 범위 10^(-9) 이하로 출력하도록 하는 문제입니다.
우선 만들 수 있는 평행사변형이 없는 경우는 세 점이 한 직선 위에 위치한 경우입니다.
보통 중, 고등학교 수학에서는 세 점이 평행할 조건은 두 점 사이의 두 기울기가 같은 경우이므로, (y2-y1)/(x2-x1) = (y3-y1)/(x3-x1) 등으로 구할 것입니다.
그러나 이 문제에서 이렇게 할 경우 틀리게 되는데, 그 이유는 아래에서 설명하겠습니다.
부연 설명을 위해 그림을 하나 그려서 첨부합니다.
우선 세 점을 가지고 나머지 한 점을 잡아 만들 수 있는 평행사변형을 생각해보면, 기존 세 점을 이어 만들어지는 삼각형 2개를 이어붙인 것과 같은 형태임을 알 수 있습니다.
위의 그림을 참고하면, 안쪽에 있는 삼각형이 원래 주어진 세 점이라고 했을 때, 총 만들어질 수 있는 평행사변형은 위와 같이 3가지가 나옵니다.
안쪽 삼각형의 세 변의 길이를 d1, d2, d3라고 하면 최종적으로 만들어지는 세 평행사변형의 둘레의 길이는 2(d1+d2), 2(d2+d3), 2(d3+d1)입니다.
그러면 두 평행사변형의 둘레의 길이의 차로 나올 수 있는 값들로는 2|d1-d2|, 2|d2-d3|, 2|d1-d3|이 있습니다.
이 형태를 보면, 답은 2*(삼각형의 가장 긴 변 - 삼각형의 가장 짧은 변)으로 간단한게 얻어짐을 알 수 있습니다.
#include<stdio.h>
#include<math.h>
void swap(double *a, double *b) {
double temp = *a;
*a = *b;
*b = temp;
}
int main() {
double x1, y1, x2, y2, x3, y3, d1, d2, d3;
scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
if((y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)) {
// Do not use (y2-y1)/(x2-x1) == (y3-y1)/(x3-x1)
printf("-1.0");
return 0;
}
d1 = sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2));
d2 = sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3));
d3 = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
if(d3 > d2) swap(&d2, &d3);
if(d2 > d1) swap(&d1, &d2);
if(d3 > d2) swap(&d2, &d3);
printf("%.10f", 2*(d1-d3));
}
남은 것은 세 점 사이의 길이를 구하고, 이들을 정렬하여 가장 긴 길이에서 짧은 길이를 뺀 값을 구하는 것입니다.
우선 루트를 계산해야하기 때문에 math.h 모듈을 호출해주어야만 합니다.
위와 같이 계산을 진행해주고, 정렬까지 해준 뒤 (저는 swap 함수를 구현하여 세 번 swap을 해주었습니다.) 문제에서 10^(-9)의 오차 이내로 구하라고 하였으므로 %.10f로 출력해줍니다.
여기까지 하면 완벽하게 구했다고 생각이 들지만, 답을 제출하면 틀렸음을 알 수 있습니다.
그 이유는 -1을 출력하기 위한 (y2-y1)/(x2-x1) = (y3-y1)/(x3-x1)의 조건문이 틀렸기 때문입니다.
만약 입력으로 x 좌표가 같은 두 점을 입력할 경우 0으로 나눗셈을 하는 꼴이 되기 때문에 NaN이 나와 조건문이 제대로 작동하지 않습니다.
따라서 나눗셈이 아닌 (y2-y1)*(x3-x1) == (y3-y1)*(x2-x1)와 같은 곱셈으로 구성된 조건문을 이용해야 합니다.
1094번 : 막대기
64cm 길이의 막대기 몇 개를 합쳐 길이 X의 막대를 만드는 문제입니다.
이 때 남은 필요한 길이가 64cm보다 작은 경우, 64cm 막대를 계속 반으로 쪼개 합치는 형식으로 막대의 길이를 맞춥니다.
#include<stdio.h>
#include<math.h>
int main() {
int X, ans, frag = 32;
scanf("%d", &X);
ans = X/64;
X = X%64;
while(frag) {
ans += X/frag;
X = X%frag;
frag /= 2;
}
printf("%d", ans);
}
문제가 아주 쉬운 편인데, 그 이유는 막대의 길이가 64cm밖에 되지 않기 때문에 그냥 반으로 계속 나눠주면서 더하면 되기 때문입니다.
저의 경우 조금 더 일반화시켜 64cm 막대를 최대한 사용해주고 이후 막대의 fragment 길이를 계속해서 반으로 나누어가며 더할 수 있는지 검사하는 방식을 사용하였습니다.