[Leetcode] 118 Pascal's Triangle [Java]

https://leetcode.com/problems/pascals-triangle/

Pascal's Triangle - LeetCode

 

 

재밌어 보여서 풀었다. ㅋㅋㅋ

 

그림에서 보는 거와 같이 List안에 List를 하나 더 만들어서 푸는 문제이다.

양 끝에는 1이 주어지고 그 안에는 전에 있는 숫자들의 합이다.

그래서 생각해낸 방법이

1. for문 2개를 이용하기.
2. 맨 처음과 맨 끝은 1을 추가해 주기
3. 나머지 위치의 값을 계산하기 (현재 위치의 값은 바로 위 줄의 왼쪽 항과 오른쪽 항을 더한 값)
   
   이 순서대로 풀면 될 것 같다란 생각으로 풀었다.

class Solution {  
public List<List> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>();

        for(int i = 0 ; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();

            for(int j = 0; j < i + 1 ; j++) {
                if(j == 0 || j == i) {
                    list.add(1);
                }
                else {
                    int a = answer.get(i - 1).get(j - 1);
                    int b = answer.get(i - 1).get(j);
                    list.add(a + b);
                }
            }
            answer.add(list);
        }
        return answer;
    }
}

최근에 알고리즘을 배우면서 이해하고 있는데 도통 이해가 가지 않아서 머리 아팠는데 이런 비교적 쉬운 문제 푸니까 재밌다ㅋㅋ