곧죽어도 콛잉

https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 이번 문제도 전형적인 dp문제. 상태값을 잘 생각해보면 2가지. 병안에 한조각 짜리 개수와, 병안에 반조각짜리 개수를 기준으로 세가면 끝. 종료 조건은 병안에 한조각짜리도, 반조각짜리도 없으면 즉시 종료! W,H에 흔들리지 말고 직접 경우의 수를 완전탐색 방식으로 몇개만 세봐도 간단하게 해결된다 현재 상태에서 1번 선택 혹은 2번 선택을 이어나간다. 즉 종료조건에 도달할때는 그 경로가 유일하다!! #include..

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/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문 돌려서 푸는 문제는 아닌건 알것이다. 그렇다면 어떻게 해결해야할까?? 논리가 생각하기 어렵다,, 바로 해결 방법을 봐보자. 먼저 간단하게 살펴보자면, 최종적인..