[구름톤 챌린지] 4주차 문제18. 중첩 점

이번주는 구름톤 챌린지 문제를 찬찬히 들여다보지는 못했다. 그래서 좀 고민하다 해설을 보고 이해하려고 노력했다. 

내 시선을 끈 것은 18일 차 중첩 점 문제였다. 내가 가장 약한 다이내믹 프로그래밍이 관련된 문제라고 설명에 나와있기 때문이었다. 

 

원래 문제를 풀 때 세로선이나 가로선이 지나가는 칸만 리스트로 관리하려고 했다. 저번에 푼 14. 작은 노드 문제에서 전체 보드를 만들어서 보드의 칸마다 상태를 저장해 주면 저장용량이 너무 많이 필요해 효율적인 문제풀이가 아니라고 했기 때문이다. 

하지만 이번 해설지에서는 각 칸마다 지나는 선이 몇 개인지 저장하기 위해 모든 칸을 생성해 주었다. 이점이 좀 의외였다. 

 

처음에는 input을 받고 보드의 사이즈와 반직선의 갯수를 저장한 후 보드를 생성해 준다. 저번에 알아냈던 list comprehension을 (문제 15. 과일 구매) 사용해 가로선과 세로선을 count 해줄 [0, 0] array를 각 보드 칸마다 생성해 준다.

N, M = map(int, input().split())
arr = [ [ [0, 0] for _ in range(N) ] for _ in range(N) ]

# 만약 N=2라면 보드모양은 2x2
[[[0, 0], [0, 0]],
 [[0, 0], [0, 0]]]

 그리고 for 문을 이용해서 M 만큼의 input을 받아 선을 만들어주어야 하고 그때 들어온 input을 list index가 0에 시작한다는 것을 기억하고 이에 맞게 수정해준 후 어느 칸부터 선이 시작하는지 알아내면 된다.

for _ in range(M):
	y, x, d = input().split()
	y = int(y) - 1
	x = int(x) - 1

그리고 각 칸마다 배치해 준 [0, 0] array를 이용해 각 칸마다 지나가는 가로선과 세로선을 저장해 주는데, 세로선은 arr[i][j][0], 가로선은 arr[i][j][1]에 저장해 준다. 

 

d가 방향정보를 가지고 있으므로 if문에 따라 d값을 이용해 가로선과 세로선이 지나가는 칸들을 +1해 주는 것은 알겠는데 for 문의 range(x, N)같이 range() 함수에 값이 두 개 들어가 있을 경우에는 어떻게 동작하는지 잘 몰라 찾아보았다.

range()는 3가지 parameter를 가질 수 있는데 range(start, stop, step) 이렇게 가질 수 있다고 한다. 이번 문제에서는 start와 stop 값을 입력해 준 것 같다.  왜냐하면 가로선일 경우에 시작하는 블록에서부터만 선을 그어주어야, 즉 모든 가로칸에 +1을 해주는 것이 아니라 선이 시작하는 부분부터 +1을 해주어야 하기 때문에 start parameter도 입력해 준 것 같다. 

	if d == "R":
		for j in range(x, N):
			arr[y][j][1] += 1
	elif d == "L":
		for j in range(x + 1):
			arr[y][j][1] += 1
	elif d == "U":
		for i in range(y + 1):
			arr[i][x][0] += 1
	elif d == "D":
		for i in range(y, N):
			arr[i][x][0] += 1

이제 각 칸을 지나가는 가로선과 세로선은 모두 세주었으므로 교점만 구하면 된다. 

result = 0

for i in range(N):
	for j in range(N):
		result += arr[i][j][0] * arr[i][j][1]

print(result)

이때 각 칸의 arr[i][j][0] 와 arr[i][j][1]을 곱해서 결과를 합산해 준 점이 코드를 간단하게 잘 작성했다는 생각이 들었다. 

 

 

이번 문제는 오래 고민하고 스스로 풀지는 못했지만 해답지를 천천히 들여다보면서 느낀 점은, 아는 만큼 코드를 짧고 간단하고 효율적으로 쓸 수 있는 것 같다. 내가 스스로 풀었다면 range() 함수의 parameter를 이용하는 대신에 복잡하고 비효율적인 방법으로 풀었을 것 같다.