글 읽기 - 멍멍 크르르르르 컹컹 (저는 이것도 못푸는 짐승입니다.)

chminoo 2년 전 0

컹컹 크르르를ㅋㄹㅋ러럴ㅇㅇㅋㅋ (야간에 연등하고 코딩하고있는 제인생이 레전드입니다.)

크르르르르르컹컹컹 (머리가 안돌아갑니다 살려주십쇼)

아무튼

생각했던 풀이 방법은

A, B, C 세점사이에서

벡터AB 벡터AC 를 gcd 이용해서 서로소로 만들고

내적 곱한 값이 0일때 카운트 += 1

하면 될거같아서 했는데

어림도 없지 ㅋㅋ 바로 "시간초과"

뭔가 기하학적으로 생각하니까 머리가 삼각자가 된기분입니다.

느낌 쌔해서 알고리즘 분류 보니까 브루트포스길래

아.. 브루트 포스구나... 그럼 단순하게 전수탐색 하면 되겠네 ㅋㅋ루삥뽕 개쉬운 문제였네 ㅋㅋㅋ

했던 제 과거를 반성합니다.

뭔가 한점 A를 기준으로 잡고 AB, AC, AD... 벡터를 전부 생성하는건 비효율 적일거같은 기분이 드는데

어떻게 해야할지 전혀 감이 안잡힙니다... 뭔가 찬물을 끼얹나?

아무래도 이코드 느린건 (엄청큰 소수, 엄청큰 소수) 와 같은 조합이 숨어져있는거같은데...

전 전혀 모르겠습니다.

해붕이를 살려주세요...

import sys
from math import gcd


point = []
n = int(sys.stdin.readline())
for i in range(n):
    point.append(list(map(int, sys.stdin.readline().split())))
count = 0
for i in range(n):
    for j in range(n):
        if j == i:
            continue
        v1 = [point[j][0] - point[i][0], point[j][1] - point[i][1]]
        g_v1 = gcd(v1[0], v1[1])
        v1 = [v1[0]//g_v1, v1[1]//g_v1]
        for k in range(j+1, n):
            if k == i:
                continue
            v2 = [point[k][0] - point[i][0], point[k][1] - point[i][1]]
            g_v2 = gcd(v2[0], v2[1])
            v2 = [v2[0]//g_v2, v2[1]//g_v2]
            if v1[0]*v2[0] + v1[1]*v2[1] == 0:
                count += 1


print(count)

ai4youej 2년 전 0

놀랍게도 더욱 무지성인 방법으로 풀 수 있습니다

herdson 2년 전 0

뒤에 지도관이 과실 용지를 들고 계십니다.

장난이고

[아.. 브루트 포스구나... 그럼 단순하게 전수탐색 하면 되겠네 ㅋㅋ루삥뽕 개쉬운 문제였네 ㅋㅋㅋ]

가 맞긴 합니다. 그래서 골드 5입니다.

근데 이게 파이썬에서는 어떻게 최적화 할지 잘 모르겠습니다.

c/c++로 바꿔서 내시면 어느정도 최적화가 덜 되도 통과될겁니다.

chminoo 2년 전 0

자수하겠습니다... 알고리즘 분류 피타고라스 정리 타고 들어온 문제라서

정말 무지성으로 좌표 거리 구하는 브루트포스로 했었는데 실패했습니다...

삼각자로 피타고라스 머리깨고 싶습니다... 사실 삼각자 용도는 이런용도가 아니었겠습니까

"ㅋㅋ 어떻게 하면 뚝배기를 수학적으로 꺠지 ㅋㅋ"

하면서 만든 공식이 피타고라스 공식 아닌가

chminoo 2년 전 0

음머어어어어

음머어어어어어

뭔가 댓글쓰고 나니 머리가 번뜩여서

어차피 한점 기준 벡터 다구해놓고 전수탐색 하면 되겠네 ㄹㅇ ㅋㅋㅋㅋ 했었는데

안됩니다 이거

왜지

이것조차 시간초과가 뜨다니...

역시 타임머신 빨리 개발해서 피타고라스 뚝배기를 깨러가야겠습니다.

import sys
from math import gcd


point = []
n = int(sys.stdin.readline())
for i in range(n):
    point.append(list(map(int, sys.stdin.readline().split())))
count = 0
for i in range(n):
    v = []
    for j in range(n):
        if j == i:
            continue
        tempv = [point[j][0] - point[i][0], point[j][1] - point[i][1]]
        g_tempv = gcd(tempv[0], tempv[1])
        v.append([tempv[0]//g_tempv, tempv[1]//g_tempv]) // <- 이거 주석아닌데 주석처리됩니다... //연산 무시하는건가
    v_len = len(v)
    for j in range(v_len):
        for k in range(j+1, v_len):
            if v[j][0]*v[k][0] + v[j][1]*v[k][1] == 0:
                count+=1


print(count)

ai4youej 2년 전 0

상수 최적화를 해보시는건 어떨까요?

N^3을 N^3/6으로 써보세요

ai4youej 2년 전 0

그리고 여담으로, C언어의 주석 처리는 // 또는 /* */로 합니다 ㅋㅋ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

멍멍 크르르르르 컹컹 (저는 이것도 못푸는 짐승입니다.)

chminoo 2년 전 0

ai4youej 2년 전 0

herdson 2년 전 0

chminoo 2년 전 0

chminoo 2년 전 0

ai4youej 2년 전 0

ai4youej 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말