문제
접근
삼각형 모양을 왼쪽으로 붙여서 배열로 생각해보자.
칸을 채워나가는 방향은 세 가지 밖에 없다.
- 아래로 움직이는 경우
- 오른쪽으로 움직이는 경우
- 왼쪽 위방향 대각선으로 움직이는 경우
세 가지 경우에 대해 각각 구현하면 된다.
주의할 부분은 방향을 전환하는 경우가 다음 방향이 범위를 벗어나거나, 이미 칠해진 곳을 만날 때 두 가지를 고려해야한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def solution(n):
answer = [[0 for _ in range(n)] for _ in range(n)]
sum = 0
for i in range(1, n+1):
sum += i
now = 1
turn = 0
x = 0
y = 0
while now < sum:
answer[y][x] = now
if turn == 0:
if y + 1 == n or answer[y+1][x] != 0:
turn = 1
continue
y += 1
elif turn == 1:
if x + 1 == n or answer[y][x+1] != 0:
turn = 2
continue
x += 1
elif turn == 2:
if x - 1 == 0 or y - 1 == 0 or answer[y-1][x-1] != 0:
turn = 0
continue
x -= 1
y -= 1
now += 1
answer[y][x] = sum
ans = []
for i in range(n):
for j in range(n):
if answer[i][j] == 0:
break
ans.append(answer[i][j])
return ans