Project Euler Problem15

2015. 2. 17. 17:16프로그래밍/알고리즘

728x90
728x90

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]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//
//  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];
        }
    }
    
...
cs




728x90
반응형

'프로그래밍 > 알고리즘' 카테고리의 다른 글

[알고리즘] 플로이드 워샬 알고리즘  (5) 2015.07.11
Project Euler Problem8  (0) 2015.02.28
Project Euler Problem16  (0) 2015.02.24
Project Euler Problem10  (0) 2015.02.15
Project Euler Problem9  (0) 2015.02.15
Project Euler Problem5  (0) 2015.02.12
Project Euler Problem7  (0) 2015.02.05