프로그래머스 문제풀이 (알고리즘) - 등굣길

프로그래머스 문제풀이 (알고리즘) - 등굣길

시도 1 (오답)

우측 아래로만 갈 수 있기 때문에, 완전 탐색이 아니라 동적 계획법으로 풀 수 있다고 생각함

만약 하나의 칸을 node 라고 부르고 x, y 좌표까지 모든 경로의 경우의 수를

node[y][x]라고 나타낼 때

장애물이 없다는 가정하면

// 위 노드까지 경로의 경우의 수 + 좌측 노드까지 경로의 경우의 수 node[y][x] = node[y-1][x] + node[y][x-1]

위 공식이 성립

예를 들어서 다음과 같이 경로가 있다고 할 때

위와 같이 풀이 할 수 있음. 따라서 다음과 같은 풀이를 작성

public int solution(int m, int n, int[][] puddles) { int[][] node = new int[n][m]; for (int p = 0; p

시도 2 (오답)

그런데 "시도 1" 방법은 치명적인 문제가 있었는데 y = 0인 지점과 x = 0인 지점을 모두 1로 채워넣고 시작한다는 점이다.

에초에 puddle 은 x = 0 또는 y = 0 인 지점에 있을 수 있기 때문에

전부 1로 채우면 안된다.

public int solution(int m, int n, int[][] puddles) { long[][] node = new long[n][m]; node[0][0] = 1; for (int p = 0; p

위 풀이에는 문제가 있다. 가로 세로 100만 넘어가도 순식간에 데이터 범위가 int 최대 범위를 넘어가버리기 때문에 중간중간 계속 1000000007 (프로그래머스에서 제시한 숫자) 로 나누어 주어야 했는데 이 점을 간과했다.

시도 3 (정답)

코드를 조금 더 깔끔하게 만들기 위해서, 2차원 배열을 가로, 세로 1씩 더 키웠고 y = 0, x = 0인 node를 모두 0으로 채우고 x = 1, y = 1 인 지점부터 계산을 시작하니 다음과 같은 풀이가 나왔다.

public int solution(int m, int n, int[][] puddles) { int [][] node = new int [n+1][m+1]; boolean[][] isPuddles = new boolean[n+1][m+1]; node[1][1] = 1; for (int p = 0; p

from http://way-be-developer.tistory.com/251 by ccl(A) rewrite - 2021-08-09 13:00:33