SiO2whocodes

https://www.acmicpc.net/problem/9184if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a 이 문제는 -50~50 범위의 정수인 a,b,c가 주어지면 w(a,b,c)를 구해서 출력하는 문제다. 접근방법입력받는대로 계산할 수도 있지만 그러면 재귀함수를 너무 많이 호출하게 돼서 시간복잡도가 커지는 문제 -> 그래서 DP로 풀어야 하는데이번에도 다 저장해두고 사용하는 방법으로 풀었다. 그래도 계산하는 횟수가 101*101*101 정도라 시간초과가 안나는 것 같다.3차원 배열 arr[a][b][c]에 3중 반복문을 돌면서 차례차례 값을 저장한다. 숫자 하나라도 0 이하면 함숫값이 1이기 때문에 차곡차곡 ..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 동적계획법 핵심 로직 dp[i][j] = dp[i][mid]+dp[mid+1][j] + 누적합(최상위 노드값) 3중 for문을 도는데 첫번째 반복문은 gap 그러니까 범위다 start~end 범위 크기를 1부터 chapter수인 K-1개까지 반복한다. (그럼 마지막 반복문을 돌면 0~K-1까지를 구할 수 있음) 두번째 반복문은 start~end범위 내에서 start의 위치를 한칸씩 뒤로 ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net동적계획법 C++2020 하계 방학 알고리즘 스터디의 마지막을 장식할 DP 문제 knapsack 문제다!!!문제는 설명하기 입아프니 위 사진을 참고하도록 하시고이번 여름방학 스터디 마지막 문제로 knapsack 문제를 정석으로 코드를 짜보려고이 문제를 골랐다. 접근방법상향식 접근, 최적의 원리 등의 접근으로 풀이하는 대표적인 DP문제 중..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 동적계획법 C++ 오르막수 구하기 문제 접근 방법 자리수 별로 오르막수를 저장하는 배열을 사용한다. 소스코드 #include using namespace std; int main(){ int n; cin >> n; int dp[1000][10]={0}; for(int i = 0 ; i < 10 ; i++) dp[0][i] = 1; for(int i = 1 ; ..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 동적계획법 C++ 가장 긴 바이토닉 부분 수열 문제 접근 방법 가장 긴 증가하는 부분 수열과 가장 긴 감소하는 부분 수열이 중첩된 문제 0부터 i 까지의 가장 긴 증가하는 부분 수열을 구하고, i 부터 n까지 감소하는 부분 수열을 구하여 합한 값으로 구한다. 증가하는 부분 수열은 차이가 없지만, 감소하는 부분 수열은 원래는 i까지 감소하는 부분수열을 구했었는데 여기선 i부터 n까지 감소하는 부분 수열을 구한다는 점이..

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의 경우에 ..

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..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 동적계획법 C++ 이번엔 가장 큰 증가하는 부분 수열의 합 구하기 접근 방법 지난번 풀었던 가장 긴 증가하는 부분 수열과 로직이 유사하다. 차이점은 우선 합을 저장해야한다는 점과 가장 긴 부분 수열의 경우 부분 수열이 성립할 경우 길이가 1만 증가했지만 이번엔 합이어서 본인의 수 만큼 증가하므로 비교할 때 이 부분을 주의해야 했다. 소스..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 동적계획법 C++ 쉬운계단수 구하기 접근방법 1~8까지는 괜찮은데 0,9가 문제였다. 그래서 0,9 경우를 따로 계산하고 우선 기본적인 접근은 n번째 자리에 오는 0부터9까지의 숫자의 갯수를 저장하는 배열을 사용한다. 0의 개수는 이전 자리의 1의 개수 1~8(i)의 개수는 이전 자리의 i-1의 개수 + i+1의 개수 9의 개수는 이전 자리의 8의 개수 그리고 마지막에 n번째 자리에 오는 0~9의 개수를 모두 더한 값을 출력한다. 처음엔 마지막에 값을 더할때 나머지 계산을 안하고, 1~8의 경우를 저장할 때 i..

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문을 사용해야 했던 ..