본문 바로가기

알고리즘/BOJ

[Python&C++]1004-어린 왕자

https://www.acmicpc.net/problem/1004

 

1004번: 어린 왕자

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주��

www.acmicpc.net

우주선의 크기를 고려할 필요가 없고, 행성계의 경계가 맞닿거나 서로 교차하는 경우도 없고 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 없기 때문에, 출발점과 도착점이 원 안에 있을때만 행성계를 진입/이탈하게 된다.

하지만, 시작점과 도착점이 같은 행성계에 있을 경우 진입/이탈을 하지 않아도 되기 때문에, ^(XOR)을 이용해서, 시작점과 도착점이 같은 원 안에 있으면 0을 반환하도록 했다.

Python 바꾸기전 코드

for x in range(int(input())):
    a = [int(i) for i in input().split()]
    startPos = (a[0], a[1])
    endPos = (a[2], a[3])
    planetList = []
    for _ in range(int(input())):
        planetList.append([int(i) for i in input().split()])    
    count = 0
    for planet in planetList:
        distance = (startPos[0] - planet[0])**2 + (startPos[1] - planet[1])**2
        distance2 = (endPos[0] - planet[0])**2 + (endPos[1] - planet[1])**2
        count += (planet[2]**2 > distance) ^ (planet[2]**2 > distance2)
    print(count)

Python 바꾼 후 코드

for x in range(int(input())):
    a = [int(i) for i in input().split()]
    startPos = (a[0], a[1])
    endPos = (a[2], a[3])  
    count = 0
    for _ in range(int(input())):
        planet = [int(i) for i in input().split()]
        distance = (startPos[0] - planet[0])**2 + (startPos[1] - planet[1])**2
        distance2 = (endPos[0] - planet[0])**2 + (endPos[1] - planet[1])**2
        count += (planet[2]**2 > distance) ^ (planet[2]**2 > distance2)
    print(count)

바꾼후 코드가 더 빠를 것 같았는데, 이상하게 더 느렸다.(밑에 사진 참고)

C++

#include <iostream>
#include <cmath>

int main(){
    int loopNum, startX, startY, endX, endY, planetCount, planetX, planetY, planetRadius, count;
    double distance, distance2;
    std::cin >> loopNum;
    for(int i = 0; i <loopNum; i++)
    {
        std::cin >> startX >> startY >> endX >> endY;
        std::cin >> planetCount;
        count = 0;
        for(int k = 0; k < planetCount; k++)
        {
            std:: cin >> planetX >> planetY >> planetRadius;
            distance = pow((startX - planetX), 2) + pow((startY - planetY), 2);
            distance2 = pow((endX - planetX), 2) + pow((endY - planetY), 2);
            planetRadius = pow(planetRadius, 2);
            count += (planetRadius > distance) ^ (planetRadius > distance2);
        }
        std::cout << count << '\n';
    }
    return 0;
}

 

Python 틀린 이유는 같은 행성계 안에 시작점과 도착점이 있을 수도 있다는 것을 고려하지 않았기 때문이고, 

C++은 두가지 이유가 있는데, 하나는 k를 이용한 for문에서, k가 아닌 i를 건드렸다.(수정전 코드: int k = 0; i <planetCount; i++)

두번째는, count += 하는 부분에서, distance2가 아닌 distance를 입력해서 XOR때문에 뭘해도 0이 나왔다.

(수정전 코드: count += (planetRadius > distance) ^ (planetRadius > distance);)

'알고리즘 > BOJ' 카테고리의 다른 글

[Python]1194-달이 차오른다, 가자.  (0) 2020.08.10
[Python&C++]7868-해밍 수열  (0) 2020.07.11
[Python&C++]1037-약수  (0) 2020.05.19
[Python&C++]1026-보물  (0) 2020.05.18
[Python&C++]1032-명령 프롬포트  (0) 2020.05.18
[Python&C++]1003-피보나치 함수  (0) 2020.05.18
[Python&C++]1002-터렛  (0) 2020.05.18
[Python&C++]2490-윷놀이  (0) 2020.05.18