[백준 9095] 알고리즘 50일차 : 1,2,3더하기
https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 동적계획법 C++ n이 1,2,3의 합으로 구성되는 경우의 수를 구하는 문제 (조합아님) 접근 방법 n을 1,2,3의 합으로 나타내는 경우의 수는 ( n-1의 경우 + n-2의 경우 + n-3의 경우) 이다. 순서가 상관있는 문제기때문에 n-1의 경우에 +1 을 한 경우들, n-2의 경우에 +2를 한 경우들, n-3의 경우에 ..
2020. 8. 25.
[백준 11722] 알고리즘 48일차 : 가장 긴 감소하는 부분 수열
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 동적계획법 C++ 이번엔 감소하는 부분 수열이다. 접근 방법 가장 긴 증가하는 부분수열에서 감소하는 부분수열로 바뀌었을 뿐이다. 비교할때 이 점을 유의해서 비교하면 된다. 소스코드 #include using namespace std; int main(){ int n; cin >> n ; int num[n]; int le..
2020. 8. 21.
[백준 11055] 알고리즘 47일차 : 가장 큰 증가 부분 수열
https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 동적계획법 C++ 이번엔 가장 큰 증가하는 부분 수열의 합 구하기 접근 방법 지난번 풀었던 가장 긴 증가하는 부분 수열과 로직이 유사하다. 차이점은 우선 합을 저장해야한다는 점과 가장 긴 부분 수열의 경우 부분 수열이 성립할 경우 길이가 1만 증가했지만 이번엔 합이어서 본인의 수 만큼 증가하므로 비교할 때 이 부분을 주의해야 했다. 소스..
2020. 8. 20.
[백준 11053] 알고리즘 45일차 : 가장 긴 증가하는 부분 수열
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 동적계획법 C++ 가장 긴 증가하는 부분 수열을 구하는 문제 접근 방법 DP라서 뭔가 2중 for문은 안될 것 같다고 생각하다가 최대 N이 1000이고 제한시간이 1초면 2중 for문도 되겠다 싶어서 그렇게 구현했다. 이번에도 각 인덱스 까지의 최대길이를 갖고 있는 배열을 사용했다. 다만 2중 for문을 사용해야 했던 ..
2020. 8. 17.
