[코드트리] 밭에 자라는 나물

dx,dy 테크닉으로 육각형 밭의 크기를 구하면 되는 문제이다.

처음 시작 위치를 (x,y)=(0,0)좌표에서 시작한다고 생각하고 문제를 풀었다.

 

https://www.codetree.ai/training-field/search/problems/vegetables-growing-in-the-field?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

CNT = 6

k = int(input())
area = 0
coord = []
dxdy = [(0,0),(1,0),(-1,0),(0,-1),(0,1)]
minX,minY,maxX,maxY=0,0,0,0

for i in range(CNT):
    _dir, dis = map(int, input().split())
    sx,sy = 0,0
    if len(coord):
        sx,sy = coord[-1][0], coord[-1][1]
    x,y = sx+(dxdy[_dir][0]*dis), sy+(dxdy[_dir][1]*dis)
    
	# x,y 각각의 min max를 구하는 로직
    if x > maxX:
        maxX = x
    if x < minX:
        minX = x
    if y > maxY:
        maxY = y
    if y < minY:
        minY = y

    coord.append((x,y))

# 꺾이는 부분과 연결된 꼭지점 두개를 구함
mid_left,mid_right=0,0
for i, (x,y) in enumerate(coord):
    if minX < x < maxX and minY < y < maxY:
        mid_left = coord[i-1]
        try:
            mid_right = coord[i+1]
        except:
            mid_right = coord[i+1-CNT]
        break

area = abs(maxX-minX)*abs(maxY-minY)
empty_area = abs(mid_left[0]-mid_right[0])*abs(mid_left[1]-mid_right[1])

print((area-empty_area)*k)

 

dx,dy 테크닉으로 밭의 각 꼭지점의 좌표를 계산해 coord 배열에 넣어주었다.

밭에서 가장 중요한 부분이 안쪽으로 꺾이는 부분의 좌표를 구하는 것인데, 도형을 이리저리 그려본 결과 꺾이는 부분은 무조건 x,y의 min과 max값 사이에 있다는 것을 알았다. 그래서 x,y 각각의 min,max값을 구하는 로직도 추가했는데 이는 min,max값으로 꺾이는 부분의 꼭지점을 구하기 위함이다.

 

처음에는 꺾이는 꼭지점의 인덱스만 가지고 empty_area를 계산했는데 그래서 index문제로 런타임에러가 났다. 그래서 꺾이는 꼭지점과 연결된 왼쪽,오른쪽 꼭지점을 찾아서 문제를 해결했는데, 좀 더 쉽고 직관적인 방법은 없을지 고민되었다. 

 

의외로 수학 좌표 관련 문제가 시뮬레이션 문제보다 오래걸렸다... 시뮬레이션만 풀고 이런 유형은 잘 안풀어서 그런거 같다.... 편식하지 말고 다 먹어치우자~!!

 

그리고 이 문제는 릴레이로 푼 문제인데, 학습하기 이외의 문제들은 국대 해설을 볼 수 없는거같다... 해당 문제의 국대 해설을 볼 수 없는 건 좀 아쉽다.... ㅠㅠ