[Programmers]등굣길/JS

⭐️ 문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

⭐️ 접근방법

문제를 읽자마자 고등학교 확통이 생각났다.
제일 윗줄과 왼쪽줄을 1로 채우고, 아래로 내려가면서 위의 값과 왼쪽 값을 더해주는 방식으로 풀었다.
물에 잠긴 지역(puddles)가 있는 곳은 0으로 채워줬다.

⭐️ 첫번째 시도

function solution(m, n, puddles) {
    var answer = 0;
    const NUM = 1000000007;	
    let dp = Array.from(Array(n), () => Array(m).fill(1));	//이차원 배열을 1로 채워줌
    
    for (let p of puddles){		//웅덩이가 있는 곳은 0으로 채워줌
        let x = p[0]-1;
        let y = p[1]-1;
        
        dp[y][x]=0;
    }
    
    for (let i=1;i<n;i++){	
        for(let j=1;j<m;j++){
            if(dp[i][j] == 0) {		//웅덩이 있는 곳은 패스
                continue;
            }
            dp[i][j]=dp[i-1][j]%NUM+dp[i][j-1]%NUM;	//위와 왼쪽값을 더해줌
        }
    }      
    
    answer=dp[n-1][m-1];
    return answer;
}

 

???? 충격.

어떻게 하나만 맞을 수 있지..

방법이 생각이 안나서 코드를 찾아볼까 하다가 먼저 질문하기 페이지를 가서 찾아봤다.

 

응? 이걸 생각 못했다... 

이차원 배열을 사용하는 문제를 풀면 항상 x, y 좌표가 헷갈렸는데 또 실수했다.. ㅠㅠ

 

⭐️ 두번째 시도

음.. x, y 좌표를 바꿔서 통과가 늘어나긴 했는데 그래도 이 방법이 아니였나보다

또 열심히 찾아본 결과

아..... 마지막 말이 내 상황이였다...ㅠㅠ

결국 코드를 다 고치기로 마음먹었다. 

 

그렇게 해서 마지막 수정을 했다.

⭐️ 정답코드

function solution(m, n, puddles) {
    var answer = 0;
    const NUM = 1000000007;
    let dp = Array.from(Array(n), () => Array(m).fill(0));	//이차원 배열을 0으로 채워줌
    
    dp[0][0] = 1;	//시작하는 곳을 1로 설정
    
    for (let p of puddles){		//웅덩이가 있는 곳은 -1로 채워줌
        let x = p[1]-1;
        let y = p[0]-1;
        
        dp[x][y] = -1;
    }
    
    for (let i = 0; i < n; i++) { 
        for (let j = 0; j < m; j++) { 
            if (dp[i][j] === -1) {	//웅덩이가 있는 곳이라면 0으로 설정
                dp[i][j] = 0;	
                continue;
            }
            if (i > 0)
                dp[i][j] += dp[i - 1][j] % NUM ;
            if (j > 0)
                dp[i][j] += dp[i][j - 1] % NUM ;
            dp[i][j] %= NUM;
        }
    }      
    
    answer = dp[n - 1][m - 1] % NUM;;
    return answer;
}

1. 1로 채웠던 이차원 배열을 0으로 채워준다.
2. 웅덩이가 있는 부분을 0이 아닌 -1로 설정해서 한 번 거르고 이후 반복문을 돌면서 0으로 처리해준다.
3. 시작점을 1로 채워주고 반복문을 돌면서 현재의 값과 위 또는 왼쪽의 값을 더해준다.

여기서 주의할 점은 계산할 때마다 %NUM으로 나눠줘야한다는 점이다.

아니면 효율성에서 다 탈락이 된다.

 

근데 대박인 사실을 발견했다.

위의 코드가 아무리 봐도 맞는데 계속 오답이 뜨길래 뭐가 문제인가하고 계속 코드를 봤다.

answer = dp[n-1][m-1] % NUM; 

이 부분에서 %NUM이 필요한가? 싶어서 %NUM을 뺐더니 정답이 되는거였다..!

근데 똑같은 코드로 한 번더 제출했는데 오답 떴음ㅋ 

근데 %NUM 붙이니까 갑자기 정답됨ㅋ

 

너무 화나서 주변 사람들한테 말했더니 종종 있는 일이라더라..

그래서 내 코드가 무조건 맞아!! 근데 왜 안돼!! 싶을때 3번정도 제출해보면 될 때가 있다고 들었다 ㅎㅎ...

 

⭐️ 느낀 점

오랜만에 DP 문제를 풀었는데 역시 너무 어려웠다..

코테는 역시 꾸준히 해야 감을 안잃고 풀 수 있는 것 같다는 걸 깨달았다.

요즘 안풀었더니 푸는 법을 좀 까먹은 것 같아서 다시 열심히 해보기로 마음 먹었다!!