알고리즘 공부를 본격적으로 시작하고 거의.. 처음으로? 이런 기분을 느꼈다.
그게 무슨 기분이었는지 자세히 써보려 한다.
알고리즘 고수 분들은 이 글을 보는 내내 너무 답답한 나머지, 샷건을 참지 못할 수 있습니다. 참을성이 부족하신 분들은 뒤로가기를 눌러주시길 바랍니다.
처음 이 문제를 봤을 때 어떻게 풀어야 할 지 감이 안왔다. 조금 과장을 보태자면 20분..? 30분 정도 멍하니 문제를 쳐다보기만 했다.
다행히? 어떻게 풀어야 할 지 감이 슬슬 잡히기 시작했고 마침내 문제의 핵심을 짚어냈다.
행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다. ~~
이 말의 의도?를 정확하게 파악했다 (맞는지는 모른다ㅎㅎ 그냥 내 생각^^)
여러 개가 막 복잡하고 다닥다닥 붙어있고 그래도 그 사이로 어떻게든 비집고 갈 수 있구나
이렇게!!! (너무나 당연하다 생각할 수 있지만 나로썬 엄청난 발견이었다..)
그러고 곧바로 이 문제에서 가~~장 중요한 핵심(키 포인트)를 캐치했다.
출발점이나 도착점 둘 중에 하나만 해당 행성안에 들어가 있으면 되구나!!!!
그제서야... 드디어...!! 코드를 끄적이기 시작했고... ?
answerList = []
for _ in range(int(input())):
x1, y1, x2, y2 = map(int, input().split())
# print("x1, y1, x2, y2 = ", x1, y1, x2, y2 );
answer = 0
for i in range(int(input())):
cx, cy, r = map(int, input().split())
# print("cx, cy, r = ", cx, cy, r)
# if (x1 < cx-r < x2 and x2 < cx+r) or (y1 < cy-r < y2 and y2 < cy+r):
# answer += 1
# if (cx-r < x1 and x1 < cx+r < x2) or (cy-r < y1 and y1 < cy+r < y2):
# answer += 1
if (cx-r < x1 < cx+r) or (cx-r < x2 < cx+r):
if not ((cx-r < x1 < cx + r) and (cx-r < x2 <cx+r)):
answer += 1
# elif (cy-r < y1 < cy+r) or (cy-r < y2 < cy+r):
# answer += 1
answerList.append(answer)
for a in answerList:
print(a)
그 때의 코드가 없어졌다..ㅜㅠ (어제 풀었던 코드라 그래요..)
대충 위의 코드와 비슷했던 것 같다.
당연히? 틀렸습니다가 나왔고
(테스트 케이스를 통과 했었는지도 기억나질 않는다. 계속 풀다가 도저히 안되겠다싶어서 GG하고 그냥 자버렸다고 절대 말 못함 ㅋ)
하지만 불굴의 서지원, 출발점과 도착점 모두 행성계 안에 있을 때도 조건을 통과해버린다는 걸 깨우치고!!!!
이제 진짜 정답이다. 하 드디어 풀었네 ㅋㅋ 진짜 고생했다... 그래 답지 안보고도 풀 수 있잖아? 하고 바로 제출.
이 때 멈췄어야 했다. 대가리 박은 시간이 아깝다는 생각을 이전부터 계속 했지만 그래도 여기서 멈췄어야 했다.
answerList = []
for _ in range(int(input())):
x1, y1, x2, y2 = map(int, input().split())
# print("x1, y1, x2, y2 = ", x1, y1, x2, y2 );
answer = 0
for i in range(int(input())):
cx, cy, r = map(int, input().split())
# if ((cx-r < x1 < cx+r) and (cy-r < y1 < cy+r)) == True:
# if ((cx-r < x2 < cx+r) and (cy-r < y2 < cy+r)) == False:
# # 출발점만 안에 있는 경우
# answer += 1
# continue
# if ((cx-r < x2 < cx+r) and (cy-r < y2 < cy+r)) == True:
# if ((cx-r < x1 < cx+r) and (cy-r < y1 < cy+r)) == False:
# # 도착점만 안에 있는 경우
# answer += 1
# continue
if (cx-r < x1 < cx+r) and (cy-r < y1 < cy+r) and (cx-r < x2 < cx+r) and (cy-r < y2 < cy+r):
continue
elif (cx-r < x1 < cx+r) and (cy-r < y1 < cy+r):
answer += 1
elif (cx-r < x2 < cx+r) and (cy-r < y2 < cy+r):
answer += 1
answerList.append(answer)
for a in answerList:
print(a)행성계(원)이 들어왔을 때 해당 좌표를 기준으로 범위를 체크한다. 총 3가지 경우가 나올 수 있다.
-
출발점만 행성 안에 있는 경우
=> (행성 x 좌표 - 반지름) < 출발점 < (행성 x 좌표 + 반지름) -
도착점만 행성 안에 있는 경우
-
둘 다 행성 안에 있는 경우
진짜 무조건 정답일거라 생각했다. 도저히 예외가 없다 생각했다. 테스트 케이스도 모두 완벽히 패스했다.
진짜 온갖 생각을 다했다. 도대체 왜 안될까. 뭐가 문제일까.
아 혹시 등호 때문인가? 에이 설마... 하고 또 삽질 시작..
=> "출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다" 라는 문제의 조건을 봤을 때 범위를 체크할 때 등호는 필요없음을 알 수 있다.
아니 도대체 뭐가 문제란 말인가...
이렇게 삽질을 하고 있을 무렵, 옆에서 채원이가 풀었다고.. 씨익 웃는다. 나는 바로 어떻게 풀었냐고 물었다. 아니 내가 푼 방식 자체가 틀렸냐고 물었다.
맞대.. 똑같대.. 아니 그럼 왜 안되냐고 ㅡㅡ
살짝 아주 조금은 다르다고 했었다. 접근 방식은 똑같은데 채원이는 점과 점 사이의 거리 공식을 이용해서 거리를 구하고 반지름과의 거리와 비교해서 풀었다. 근데 좌표로 길이 계산 (x y 각각) 해준거랑 그거랑 뭐가 다른 지를 진짜 도저히 모르겠더라... 30분 동안 채원이랑 같이 머리를 굴렸는데 도저히 예외를 찾지 못했다.
그러고 정현이 형한테 도움을 청했다.. 왜 안되냐고...
고집이라... 아니다 싶을 때 이미 늦었다 싶을 때 그 때 바로 돌아서야 했다. 구글링 했어야 했다. 하지만 그 때 조차도 이미 늦었다 생각했다. 이렇게까지 시간을 썼는데 답지 봐버리면 그 시간들이 너무나 정말 너무나 아까울 것 같아서 답지를 보지 못했다. 그리고 내가 풀이한 방식에서 도저히 틀릴 만한 부분, 예외를 찾지 못해서 더 고집을 부렸던 것도 물론 있다.
밥 먹으러 가서 답장을 봤는데 예외가 존재하더라
나는 진짜
진짜 어떡하지?
까맣게 색깔 칠한 부분이 바로 예외다. 나는 지금껏 사각형이라고만 생각했던 것이다. 점과 점사이의 거리로는 되지만 좌표상으로의 거리 계산으로는 안되는 이유가 바로 이것이다.
진짜 너무 억울하고? 화가 났는데? 또 반대로 기분이 졸라 좋으면서? 사이다 2L 들이붓고 10초동안 트름을 한거 마냥 시원했다.
answerList = []
for _ in range(int(input())):
x1, y1, x2, y2 = map(int, input().split())
# print("x1, y1, x2, y2 = ", x1, y1, x2, y2 );
answer = 0
for i in range(int(input())):
cx, cy, r = map(int, input().split())
# if (cx-r < x1 < cx+r) and (cy-r < y1 < cy+r) and (cx-r < x2 < cx+r) and (cy-r < y2 < cy+r):
# # 둘 다 안에 있는 경우
# continue
# if (cx-r < x1 < cx+r) and (cy-r < y1 < cy+r):
# # 출발점만 안에 있는 경우
# answer += 1
# if (cx-r < x2 < cx+r) and (cy-r < y2 < cy+r):
# # 도착점만 안에 있는 경우
# answer += 1
if (((cx-x1)**2 + (cy-y1)**2) ** 0.5) < r:
if (((cx-x2)**2 + (cy-y2)**2) ** 0.5) > r:
answer += 1
if (((cx-x2)**2 + (cy-y2)**2) ** 0.5) < r:
if (((cx-x1)**2 + (cy-y1)**2) ** 0.5) > r:
answer += 1
answerList.append(answer)
for a in answerList:
print(a)정현이 형이 말한대로 1시간 이상 짱구 굴렸는데 안되면.. 에이 그래도 1시간은 너무 했다. 2시간! 2시간 이상 짱구 굴려도 안되면 그냥 다른 사람 풀이보고 내 걸로 만들자. 그게 훨씬 효율이 좋을 것 같다.
하지만 나는 이렇게 머리 박으면서.. 보이지 않는 예외를 마주하면서 짱구 굴리는 시간도 물론 중요하다고 생각한다.
(누굴 저격하거나 비하하는건 절대 아닙니다. 그냥 이런 사람들도 분명히 있을 것 같다는 주관적인 생각에, 나는 그러지 않았으니 이렇게 삽질 한거도 나름 괜찮다고.. 의미 있다고 그냥 자위하는거에요^^)
이런 과정도 없이 조금만 생각해보고 에이 모르겠다~ 하고 바로 구글링해보고 답지를 찾아보면 물론 시간은 단축될 것이다. 말도 안되게 단축 될 것이다. 하루에 1문제를 겨우겨우 풀고 다시 풀이를 정리해왔지만 전자와 같은 방법으로는 하루에 2개 3개 4개씩도 풀 수 있다.
하지만 그럴 경우 그 삽질하는 과정에서 얻을 수 있는, 눈에 보이진 않지만, 무수히 많은, 직접 경험하지 않고서는 깨달을 수 없는 "무언가"를 찾을 수 없다. 특히 지금, 알고리즘 공부를 제대로 시작한 지 얼마 안된 상황에서는 더욱이 그렇다. (조금이나마 실력이 뒷받침되는 단계부터는 상관없다고 생각하고 당연히 전자와 같은 방법을 채택하여 적용해야 한다고 생각한다. 시간은 금이니까)
그렇다.
다이아3도 아니고, 플레 3도 아니고, 골드 3도 아닌 고작 실버 3짜리 기하학 문제, 수학 문제 하나 풀고 쓰는 글인데 이렇게 장황하게 쓰는 이유가 무엇이냐?
√2 ( 발생할 수 있는 예외 ) 이 간단한 걸 생각 못해서.. 대가리 박고 삽질한 시간이 너무 아까워서.. 그래도 그 시간들은 절대로 그냥 갖다 버린 시간이 아니었음을 자위하고자 함이다.
