82. 멀리 뛰기

 

기본 틀 :

public class Solution {
    public long solution(int n) {
        long answer = 0;
        return answer;
    }
}

 

처음에는 조합을 이용해서 문제를 해결할려고 했다.

 

이유로는,

 

n = 7일 때,

 

1111111 => 7C7 = 1

111112 => 6C5 = 6

11122 => 5C3 = 10

1222 => 4C1 = 4

 

=> 21

 

n = 6일 때,

 

111111 => 6C6 = 1

11112 => 5C4 = 5

1122 => 4C2 = 6

222 => 3C0 = 1

 

=> 13

 

로 n이 짝수이면 3C0과 같은 케이스를 위해 1을 더해주면 원하는 결과 나올 것이라 생각했기 때문이다.

 

하지만, 위의 방법을 코드로 작성하기는 번거롭고 불필요한 과정을 더 추가하는 행위였다.

 

왜냐하면,

 

n = 1

1

=> 1

 

n = 2

11

2 

=> 2

 

n = 3

111

12

21

=> 3

 

n = 4

1111

112

121

211

22

=> 5

 

와 같이 결과를 잘 보면 이전 결과와 그 이전 결과의 합이 내가 원하는 n의 횟수였기 때문이다.

 

그래서, List를 선언과 동시에 1과 2를 할당해주고,

 

반복문을 통해 n에 해당하는 경우의 수를 구하면서

 

OverFlow를 방지하기 위해서 해당 결과에 % 1234567를 해줬다.

 

using System;
using System.Collections.Generic;


public class Solution {
    public long solution(int n) {
        List<int> list = new List<int>() {1, 2};
        
        for(int i = 2; i < n; i++)
            list.Add((list[i - 1] + list[i - 2]) % 1234567);
        
        
        return list[n - 1];
    }
}