곧죽어도 콛잉

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이번 문제는 그냥 dp하나만 보면 간단하게 풀릴 수 있었는데 .. 최소값을 구하는 것 뿐만 아니라 최솟값이 나오기까지의 과정도 보여줘야한다. 즉, dp 진행 중, 중간의 값들을 계속해서 "Tracing" 해야한다. 다행스럽게도, 잘 생각해보면 특정값 X는 최소의 연산횟수를 보장하는 경로가 단 한가지 연산 밖에 없다. (여러 경로가 있지만, 그럼에도 최선의 선택은 1개뿐.) 예를 들어, 10의 경우는 9, 9의 경우는 3, 3의 경우는 1이 전부다. 10 9 3 1 즉 이것을 새로운 DP의 값으로 보여줄..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 이 문제도 이전에 풀었던 DP와 같은 유형!! 값을 거꾸로 타고 올라가면서 계속해서 값을 갱신해나가면 된다! 계속해서 dp 배열에 넣는 논리는 똑같은데, dp에 저장할 상태값은 현위치, 왼발위치, 오른발위치로 정의해줄 수 있다. 그리고 추가적으로 가해지는 힘이 달라지는 부분 구현은 최대한 간단한 것부터 구현해나가면 편하다. po 함수를 유심히보자! #include..

https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 기본적인 dp 문제! 먼저 시간복잡도만 계산해보면 100개의 구간 각각이 2개씩 가능하므로, 2^100이라는 큰 수가 나온다. 따라서 DP를 써야할 수 밖에 없다. 그래프를 진행할수록 반드시 필요한 2가지 상태값이 있다. 1. 현재 구간 위치 2. 지금까지의 소요시간 이것을 바탕으로 해당 경로가 가질 수 있는 최대값을 유추할 수 있다. 다음처럼 그래프를 그..

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 모르면 한도끝도 어려운 LCS 문제! DP에 속하지만 따로 분류해서 공부하도록한다. 우선 O(N^2) 풀이부터 풀어보자. 이 부분은 코드 이해가 어려워서 그림으로 표현해봤다. 우선, 이 문제는 값을 저장할 배열 arr과, 현재 LCS 상태를 저장하는 cnt 배열이 필요하다. 값 하나를 볼때마다 LCS를 계속 업데이트해가..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제도 앞에서 푼 것과 같은 문제이다. (1,2,3 더하기 4) K라는 가치를 만들기 위해 값들을 더하는 경우의 수를 구하는 것이다!!! 동전은 무한대로 사용할 수 있다는 점을 명시하라! #include using namespace std; int dp[100001], n, k, t; int main(){ cin >> n >> k; dp[0]=1; for(int i = 0 ; i < n ; i+..

https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 오랜만에 올린다 ㅠ 블로그에 글 열심히 써야겠다. DP가 너무 어려워서 천천히 해가는 중이다.. DP는 브루트포스, 백트래킹 안되면 해야하는 친구이다. 이 문제는 3중 for문 돌려서 푸는 문제는 아닌건 알것이다. 그렇다면 어떻게 해결해야할까?? 논리가 생각하기 어렵다,, 바로 해결 방법을 봐보자. 먼저 간단하게 살펴보자면, 최종적인..