자료구조&알고리즘/백준

[C++] 백준 16395번 - 파스칼의 삼각형

celinayk 2023. 7. 29. 00:23
반응형

원래 내 코드는

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <limits.h>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;

int main()
{
    int n, k;
    cin >> n;
    cin >> k;
    
    if (n == k) {
        cout << 1;
    }
    else if (k == 1) {
        cout << 1;
    }
    else {
        int a = (n - 1) * (n - 2);
        int b = k - 1;
        cout << a / b;
    }

    return 0;

}

그냥 경우의 수를 나눠서 풀었다 근데 틀렸단다...

분명 예제에 있는 숫자는 다 맞았는데 왜 틀렸는지 모르겠음

그래서 다른사람들의 풀이방법을 참고해서 다시 풀었다

 

이번엔 배열로 풀었다

이차원 배열을 만들고 파스칼의 삼각형을 만들어본다

근데 저걸 전부 왼쪽으로 땡겨오면 된다 >> 문제 해결 포인트

1. 맨왼쪽에 1을 먼저 채워준다

2. 파스칼의 삼각형 공식을 이용해서 위에서부터 계산하면서 내려온다!

노란색부분은 저절로 1로 고정되게 되서 따로 구하지 않아도 됨 >> 이건 몰라서 첨에 쟤도 구할려고했음

원래 파스칼의 삼각형의 규칙이 맨오른쪽값들은 항상1이라서 자연스럽게 1이 되는것  

 

최종코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <limits.h>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;

int arr[31][31];

int main()
{
    
    int n, k;
    cin >> n >> k;

    for (int i = 0; i < 31; i++) {
        arr[i][0] = 1;
    }
    
    for (int i = 1; i <31; i++) {
        for (int j = 1; j <=i; j++) {
            arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
        }
    }
  
    cout << arr[n - 1][k - 1] << endl;


    return 0;


}

출처

https://www.acmicpc.net/problem/16395

 

16395번: 파스칼의 삼각형

파스칼의 삼각형은 이항계수를 삼각형 형태로 배열한 것인데, 블레즈 파스칼(1623-1662)을 따라 이름 붙여졌다. 단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다. N번째 행

www.acmicpc.net