안녕 세상아,

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 11053번 문제랑 같은 문제라고 생각하면 된다. dp를 이용해서 문제를 해결하였다. #include #include using namespace std; int arr[1001]; int dp[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 다이나믹 프로그래밍을 사용하여 이항계수를 구하는 문제이다. 다이나믹 프로그래밍을 사용하는 이유는 범위가 1000 이하이기 때문이다. dp로 이항계수 점화식을 만들면 끝이다. #include #include using namespace std; int n, k; int arr[1001][1001]; int main() { cin >> n >> k; arr[0][0] = 1; arr[1][0] = 1; arr[1][1] = 1; for (int i = 2; i

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp의 순서를 찾아준 후 최댓값을 따로 만들어서 풀어주었다. 생각보다 쉽게 풀었다. 순서는 첫번째 빼고 (dp의 직전 값과 arr의 현재 값을 더해준 것, arr의 현재값)을 비교해서 더 큰 값을 dp에 넣어주면 된다. 고려해야될 것은 계속하다보면 가장 큰 합이 구해졌는데 음수를 계속 더해서 작아지는 경우가 있다. 이런 경우를 대비하여 큰 수를 갱신할 maxCount값을 만들었다. #include #incl..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 규칙 찾는 다이나믹 프로그래밍은 너무 어려워.. #include #include using namespace std; int arr[1001]; int dp[1001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin ..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 규칙 찾기 약간 조금 까다로웠다. 사실 그냥 내가 규칙 찾기 잘 못하는 것 같다. 규칙은 p(n) = p(n-2) + p(n-3) 이다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long int t, n; cin >> t..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 첫번째 계단일 때와 두번째 계단일 때는 고민 없이 구할 수 있다. 하지만 세번째 계단부터는 연속해서 3개 계단을 오를 수 없는 규칙이 있기 때문에 고민을 해야한다. 세번째 계단을 오르기 위해서는 1. 시작 -> 첫번째 계단 -> 세번째 계단 2. 두번째 계단 -> 세번째 계단 이렇게 두가지 경우가 있다. 이 중 더 큰 한가지를 선택해야되기 때문에 max(1,2) 이렇게 볼 수 있다. #include #incl..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net dp 기본 문제. int 값 범위 넘어가는 것만 신경써주면 쉽게 풀 수 있다. #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long int dp[1001]; dp[1] = 1; dp[2] = 2; for (long long int i = 3..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 그냥 쉽게 생각해서 2중 for문 사용했는데 역시나 시간초과로 틀림 ㅎㅎ;; 틀리는게 당연함 입력값 최대가 N, M 둘다 100,000임 #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 세상에는 똑똑한 사람이 너무 많다..물론 내가 바보일지도? 처음부터 생각하느라 뇌정지왔는데 거꾸로 풀면 간단하게 풀린다. ex) n=7, 아래와 같이 day와 cost가 주어질 때 맨 뒤부터 풀게되면 i=7일 때 date=7+2 이기 때문에 n보다 큰 수여서 dp가 0이 된다. i=6일 때도 date=6+4 이기 때문에 n보다 큰 수여서 dp가 0이 된다. 1일 2일 3일 4일 5일 6일 7일 day 3 5 1 1 2 4 2 cost 10 20 10 20 15 40 200 dp 0 0 i=5일 때부터는 date가 n을 넘어가지 않기 ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net #include #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t; cin >> t; int zero[45] = {}; int one[45] = {}; zero[0] = 1; zero[1] = 0; one[0] = 0; one[1] = 1; for (int i = 2; i < 45; i++) { zero..