글 읽기 - 제가 생각한 방법이 어떤 이유로 틀린건지 궁금합니다...

specialjin1 5년 전 0

route는 주어지는 지도의 배열이구요

num_route는 경로의 수를 저장한 배열입니다.

제가 생각한 방법은 위쪽, 왼쪽, 오른쪽으로 갈 수 있다면(현재값보다 값이 작다면) 그 쪽으로 가는 길이 생기는거니 경로값을 더해주는 식으로

쭉 내려왔는데요 정리하면 이렇습니다.

밑으로 내려올 수 있으면(route[i][j]<route[i-1][j]) 밑의 값에 경로를 추가(num_route[i][j]+=num_route[i-1][j])해줍니다.
왼쪽으로 갈 수 있으면(route[i][j]>route[i][j-1]) 왼쪽 경로에 현재의 경로를 추가(num_route[i][j-1]+=route[i][j])해줍니다.
오른쪽으로 갈 수 있으면 (route[i][j]>route[i][j+1]) 오른쪽 경로에 현재의 경로를 추가 (num_route[i][j+1]+=route[i][j]) 해줍니다.

코드는 잘못 짠게 아닌 것 같은데.. 이 아이디어의 어디가 잘못된 걸까요... 아무리 생각해도 반례를 못 찾겠습니다

n, m = [int(x) for x in input().split()]
num_route = [[0]*m for x in range(n)]
route = [[0]*m for x in range(n)]
num_route[0][0] = 1
for i in range(n):
    route[i] = [int(x) for x in input().split()]

for i in range(m):    # 첫 줄 초기화 -> 오른쪽 끝까지
    if route[0][i]<route[0][i-1]:
        num_route[0][i] += num_route[0][i-1]

for i in range(1,n):
    for j in range(m):
        if route[i][j]<route[i-1][j]:    # 밑으로 내려오기
            num_route[i][j]+=num_route[i-1][j]
    for j in range(m-1):    # -> 오른쪽 끝까지 가기 (0~m-2까지)
        if route[i][j]>route[i][j+1]:
            num_route[i][j+1]+=num_route[i][j]
    for j in range(m-1,0,-1):   # <- 왼쪽 끝까지 가기 (m-1~1까지)
        if route[i][j]>route[i][j-1]:
            num_route[i][j-1]+=num_route[i][j]

print(num_route[n-1][m-1])

specialjin1 5년 전 0

아하 제가 문제를 착각한거군요... 감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 생각한 방법이 어떤 이유로 틀린건지 궁금합니다...

specialjin1 5년 전 0

specialjin1 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말