자료구조&알고리즘/백준
[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