취준생의 코딩테스트 연습기

[백준] 11048번 파도반 수열 / 파이썬(python) 본문

코딩테스트/백준

[백준] 11048번 파도반 수열 / 파이썬(python)

Jiwon_C 2021. 3. 20. 22:14

# 문제 링크

www.acmicpc.net/problem/11048

 

11048번: 이동하기

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는

www.acmicpc.net

# Soultion (실패)

재귀를 이용하여 문제를 풀었는데, 런타임 에러 (RecursionError)가 발생하였다.

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
n,m = map(int, input().split())
li = []
 
for _ in range(n):
    li.append(list(map(int,input().split())))
    
max_candy = 0
candy = []
def miro(x,y):
    global max_candy
    if x==n-1 and y==m-1:
        candy.append(li[x][y])
        if sum(candy) > max_candy:
            max_candy = sum(candy) 
        candy.pop()
        return 
    
    if (0<=x and x<n) and (0<=y and y<m):
        candy.append(li[x][y])
        miro(x+1,y)
        candy.pop()
        candy.append(li[x][y])
        miro(x,y+1)
        candy.pop()
        candy.append(li[x][y])
        miro(x+1,y+1)
        candy.pop()
    else:
        return
    
miro(0,0)
print(max_candy)
 cs

 

# Soultion (성공)

DP(동적프로그래밍)을 이용하여 문제해결

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n,m = map(int, input().split())
li = []
 
li.append([0]*(m+2))
for _ in range(n):
    li2 = [0]+list(map(int,input().split()))+[0]
    li.append(li2)
    
li.append([0]*(m+2))
 
for i in range(1,n+1):
  
    for j in range(1,m+1):
        max_num = max(li[i-1][j], li[i][j-1],li[i-1][j-1])
        li[i][j] = max_num+li[i][j]
        
print(li[n][m])
 cs

4. 9. n*m 배열의 테두리를 0으로 채워주어 index에러가 나지않도록 만들어줌

14. 3가지 방향에서의 제일 큰 값을 구해 li에 저장

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 10773번 제로 / 파이썬(python)  (0) 2021.03.23
[백준] 10828번 스택 / 파이썬(python)  (0) 2021.03.23
[백준] 9461번 파도반 수열 / 파이썬(python)  (0) 2021.03.16
[백준] 1904번 01타일 / 파이썬(python)  (0) 2021.03.16
[백준] 9184번 신나는 함수 실행 / 파이썬(python)  (0) 2021.03.14
'코딩테스트/백준' Related Articles more
Comments