.png&blockId=3197e115-ee0d-4d9c-9f5d-4b57cb28634e)
정수 삼각형
접근방법
1.
triangle 이중 리스트에 이전값과 자신의 값을 더하는 과정을 고려해보았다. (단, 값을 이동할 때 이전의 값을 사용하다보니 첫번째 행이 아닌 두번째 행부터 for문을 돌려야 한다.)
memoization방식을 위해 dp 이중리스트를 만들까 생각했지만, 위의 방법이 더 나아 보였다.
2.
값을 바꿀 때 들어올 수 있는 값중 큰 값을 받도록 했다.
a.
leftdown은 이전행과 지금행의 합을 구하는 것이다.(단 맨 왼쪽에 있는 값은 leftdown만 가능)
b.
rightdown은 이전행+이전열과 지금행+지금열의 값을 더하는 것이다.(단 맨 오른 쪽에 있는 값은 rightdown만 가능)
c.
모서리가 아닌 경우는 leftdown과 rightdown중 큰 값을 받게 한다.
3.
최댓값은 마지막 행중에 가장 큰 값이므로 max(triangle[-1])식을 썻다
7 | ||||
10 | 15 | |||
18 | 16 | 15 | ||
20 | 25 | 20 | 19 | |
24 | 30 | 27 | 26 | 24 |
def solution(triangle):
for i in range(1, len(triangle)):
for j in range(len(triangle[i])):
# leftdown
if j == 0:
triangle[i][j] += triangle[i-1][j]
# rightdown
elif j == len(triangle[i])-1:
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] = max(triangle[i][j] + triangle[i-1][j], triangle[i][j] + triangle[i-1][j-1])
answer = max(triangle[-1])
return answer
Python
복사
등굣길
접근방법
1.
이동한 경우의 수를 저장할 리스트 way를 만든다
2.
물에 잠긴 지역을 표시한다
a.
-1로 표시하고 방문하고 나면 0으로 교체한다.
3.
이동할 수 있는 경우의 수를 계속해서 적립한다.
def solution(m, n, puddles):
answer = 0
way = [[0]* m for _ in range(n)]
way[0][0] = 1
for puddle in puddles:
first = puddle[0]-1
second = puddle[1]-1
way[first][second] = -1
# print(way)
for i in range(n):
for j in range(m):
if way[i][j] == -1:
continue
way[i][j] += (way[i-1][j] + way[i][j-1]) % 1000000007
print(way)
answer = way[n-1][m-1]
return answer
Python
복사
def solution(m, n, puddles):
answer = 0
way = [[0]* (m+1) for _ in range(n+1)]
way[1][1] = 1
for puddle in puddles:
first = puddle[0]
second = puddle[1]
way[second][first] = -1
# print(way)
for i in range(1, n+1):
for j in range(1, m+1):
if way[i][j] == -1:
way[i][j] = 0
continue
way[i][j] += (way[i-1][j] + way[i][j-1]) % 1000000007
print(way)
answer = way[n][m]
return answer
Python
복사
