JavaScript - CodeKata #13 πŸ“Œ

devmoonshΒ·2020λ…„ 9μ›” 28일
0

JavaScript

λͺ©λ‘ 보기
38/48
post-thumbnail

1. Question

μ–‘μˆ˜λ‘œ 이루어진 m x n κ·Έλ¦¬λ“œλ₯Ό 인자둜 λ“œλ¦½λ‹ˆλ‹€.
상단 μ™Όμͺ½μ—μ„œ μ‹œμž‘ν•˜μ—¬, ν•˜λ‹¨ 였λ₯Έμͺ½κΉŒμ§€ κ°€λŠ” 길의 μš”μ†Œλ₯Ό λ‹€ λ”ν–ˆμ„ λ•Œ,
κ°€μž₯ μž‘μ€ 합을 μ°Ύμ•„μ„œ return ν•΄μ£Όμ„Έμš”.

ν•œ μ§€μ μ—μ„œ μš°μΈ‘μ΄λ‚˜ μ•„λž˜λ‘œλ§Œ 이동할 수 μžˆμŠ΅λ‹ˆλ‹€.

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Output: 7

μ„€λͺ…: 1β†’3β†’1β†’1β†’1 의 합이 제일 μž‘μŒ

2. Answer

const minPathSum = grid => { 
    // 일단 첫 row와 첫 column은 각각, κ·Έ path둜 κ°”λ‹€κ³  μƒκ°ν•˜κ³  λ”ν•΄λ†“λŠ”λ‹€.
    for (let i = 1; i < grid.length; i++) {
        grid[i][0] += grid[i-1][0];      
    }
    
    for (let i = 1; i < grid[0].length; i++) {
         grid[0][i] += grid[0][i-1];
    }    
    
    for (let i = 1; i < grid.length; i++) {
        for (let j = 1; j < grid[0].length; j++) {
            
            //μœ„μͺ½μ΄λ‚˜ μ™Όμͺ½μ—μ„œ, 더 μž‘μ€κ±Έλ‘œ 더해쀀닀.
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }

    return grid[grid.length-1][grid[0].length-1];
};

console.log(minPathSum([[1,2,3],[4,1,2]])); // 6
profile
Junior front-end developer

0개의 λŒ“κΈ€