세상의 변화에 대해 관심이 많은 이들의 Tech Blog search

BOJ 01000(A+B), 01001(A-B), 01002(터렛) 문제 풀이

|

목차

참조

분류 URL
문제 A+B, A-B, 터렛
이 글에서 설명하는 코드 01000~01002

BOJ 1000(A+B)

개요

시간복잡도: $ O(1) $

공간복잡도: $ O(1) $

문제 풀이

단순 구현 문제이다. 이 문제는 여러분이 어떤 식으로 이 사이트에 제출해야 하는지를 시험할 수 있는 문제이다. 아래 구현과 같이 하면 된다.

구현

다음과 같다. 이 문제는 C 스타일로 구현하였다.

#include <stdio.h>

int main(){
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d", a+b);

    return 0;
}

BOJ 1001(A-B)

개요

시간복잡도: $ O(1) $

공간복잡도: $ O(1) $

문제 풀이

이 문제 역시 단순 구현 문제이다. 이 문제도 여러분이 어떤 식으로 이 사이트에 제출해야 하는지를 시험할 수 있는 문제이다. 아래 구현과 같이 하면 된다.
사실 바로 위 문제에서 딱 한 글자만 바꿔도 된다.

구현

다음과 같다. 이 문제는 C++ 스타일로 구현하였다.

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);    cin.tie(0);
    int a,b;
    cin >> a >> b;
    cout << a-b;
}

참고로, cin, cout 함수는 scanfprintf에 비해 느리기 때문에, main 함수 첫 줄과 같은 구문을 써 주어야 한다.
ios::sync_with_stdio(false);를 썼을 때는 cincoutscanfprintf를 같이 쓰면 안 된다.


BOJ 1002(터렛)

개요

시간복잡도: $ O(1) $

공간복잡도: $ O(1) $

문제 풀이

이 문제도 구현 문제지만, 알고리즘 문제를 풀어본 경험이 별로 없으면 충분히 헷갈릴 수 있는 문제이다.

이 문제의 답의 종류는 4종류이다. 먼저 종이에 원 2개를 그려보고 답의 개수가 될 수 있는 가지수를 생각하면 답을 얻을 수 있다.

  1. 위치의 개수가 무한대인 경우는 터렛 2개가 같은 위치에 있는 경우이다. 사실은 문제 데이터가 잘못되지 않았다면 거리 r1과 r2도 같아야 한다. 답은 -1이다. 두 원이 완전히 일치하는 경우이다.
  2. 만약에 두 사람이 구한 거리의 합이 두 터렛의 거리보다 멀면 불가능하다. 비슷하게 거리의 차가 터렛의 거리보다 짧아도 불가능하다. 답은 0이다. 두 원이 만나지 않는 경우이다.
  3. 만약 터렛1, 터렛2, 마린이 일직선상에 있고 거리의 합 또는 차가 일치하면 답은 1이다. 두 원이 접하는 경우이다.
  4. 그 이외의 경우라면 답은 2이다. 두 원이 두 점에서 만나는 경우이다.

구현

다음과 같다. R과 r은 각각 거리의 합의 제곱 또는 차의 제곱이다.

#include <stdio.h>

using namespace std;

int TC;
int x1, y1, x2, y2;
int r1, r2;
int main(){
    scanf("%d",&TC);
    while(TC--){
        scanf("%d%d%d%d%d%d", &x1, &y1, &r1, &x2, &y2, &r2);
        int d_square = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2);
        int R_square = (r1+r2) * (r1+r2);
        int r_square = (r1-r2) * (r1-r2);
        if(x1==x2 && y1==y2 && r1==r2)
            puts("-1");
        else if(d_square > R_square || d_square < r_square)
            puts("0");
        else if(d_square==R_square || d_square==r_square)
            puts("1");
        else 
            puts("2");
    }
    return 0;
}