본문 바로가기

다이나믹 프로그래밍7

백준 17626번 : Four Squares [C++] 주소 : https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, num = 0; vector dp(50001, 0); cin.. 2022. 9. 4.
백준 11727 : 2xn 타일링 2 [C++] 주소 : https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 소스 코드 : #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int result = 0; cin >> n; vector v(n); v[0] = 1; v[1] = 3; for (int i =.. 2022. 9. 4.
백준 11726번 : 2xn 타일링 [C++] 주소 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 소스 코드 : #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; int result = 0; cin >> n; vector v(n); v[0] = 1; v[1] = 2; for (in.. 2022. 9. 4.
백준 9461번 : 파도반 수열 [C++] 주소 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 소스 코드 : #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; vector P(101); cin >> N; P[1] = 1; P[2] = 1; P[3] = 1; fo.. 2022. 9. 2.