Project Euler Problem15

Lattice paths

Problem 15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

나의 풀이)

1. 최단경로 구하기

좌상단의 값을 더하면 그 지점에 갈 수 있는 경로의 수가 나온다.

검은색으로 패스를 적고 이를 배열에 넣는다.

1행과 1열은 다 1로 초기화 하고 2행 2열부터 값을 계산한다.

2. 구현

Xcode로 작성했다. 배열 중간에 오버플로우로 계산이 제대로 되지 않아 int64형을 이용해 계산했다.

arr[i][j] = arr[i][j-1] + arr[i-1][j]

//
//  main.cpp
//  Problem15
//
//  Created by Jo Minhyuk on 2015. 2. 17..
//  Copyright (c) 2015년 Jo Minhyuk. All rights reserved.
//
/*
 Lattice paths
 Problem 15
 Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
 
 
 How many such routes are there through a 20×20 grid?
 
 */
 
...
    
    // search
    for (i = 1; i<21; i++) {
        for (j = 1; j<21; j++) {
            pathArray[i][j] = pathArray[i][j - 1] + pathArray[i - 1][j];
        }
    }
    
...