119. Pascal's Triangle II (C++)

요즘 업무 배우느라 너무 바빠서 개인 공부를 소홀히 한지 좀 된거 같다...

사내 스터디도 코로나 때문에 모이지도 못하고 어영부영 마무리 되버렸고...

그래서 유튜브 보면서 대충 클론코딩이라도 할까 생각중인데 그거마저도 이미 너무 게을러져서 리트코드라도 하루에 몇문제씩 풀기로 결심했다. 오랜만에 하는거라 일단은 Easy 쪽으로 하다가 Easy쪽 어느정도 풀린다 싶으면 난이도 올릴 예정이다. 또 회사에서 DB를 많이 사용하다보니까 쿼리문을 직접 짜지는 않지만(프레임워크가 해줌) 그래도 어느정도 알고는 있어야 하니까! SQL도 풀 예정이다.

이미 시작한지는 좀 지났지만 첫 게시글은 이걸로!

 

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

Pascal's Triangle II - LeetCode

문제는 n을 입력 받아서

파스칼 삼각형의 n 번째 행을 출력하면 된다.

처음에 dp로 삼각형을 n열 만큼 그려서 할까 생각했는데 이항정리 였나 정확히 기억이 안나지만... 암튼 뭐 배웠던거 기억이 나서 조합을 이용하기로 했다.

 

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans;
        if(rowIndex == 0){
            ans.push_back(1);
            return ans;
        } 
        ans.push_back(1);
        int start = 1, end = rowIndex;
        long long Calc = 1;
        for(int i=1;i<rowIndex;++i){
            Calc *= end;
            Calc /= start;
            end--;
            start++;
            ans.push_back(Calc);
        }
        ans.push_back(1);
        return ans;
    }
};

작성된 코드는 이러하다. 0을 입력받으면 1을 리턴하고 그렇지 않으면 처음과 끝에 1을 집어 넣어준다.

문제는 그 사이를 채우는 일인데 nC0... nCn-1까지를 채워야 하니까

처음 1로 시작한 다음 분자는 처음 크기로 시작해서 -1씩 해주면서 곱해주고

분모는 1로 시작해서 +1씩 하면서 나누어 준다.

이 결과값을 벡터에 넣어주면 정답!

 

 

준수한 시간!

앞으로도 하루에 한두문제는 꼭 풀어야지... 시간나면 꼭 클론코딩...