[BOJ] 1007

less than 1 minute read

벡터 매칭

1007번 https://www.acmicpc.net/problem/1007

backtracking을 이용했는데,
처음에는 점 두개를 어떻게 한번에 처리하지? 라는 생각에 사로잡혀서 시간을 엄청 날려먹다가,
함수 한번 호출 시에 점 하나씩 처리할 수는 없을까? 라는 생각이 떠올라서 아래와 같이 생각해봤습니다.

어떤 점 두개를 잇는 벡터는

  1. (점1.X - 점2.X, 점1.Y - 점2.Y)
  2. (점2.X - 점1.X, 점2.Y - 점1.Y) 의 두가지 경우가 있습니다.

따라서, 각 점은 결과 벡터를 구하는 과정에서 X, Y가 빼지거나 더해지거나이고,
뺀 점과 더한 점의 수가 같다면 뺀 점과 더한 점이 적절히 이어져 벡터가 된다고 생각하면 되기 때문에
각 점을 뺄지 말지만 함수 호출 시에 정해줬습니다.

정답 코드 https://github.com/Geniemo/BOJ/blob/master/1007.cpp

Categories:

Updated:

Leave a comment