곧죽어도 콛잉

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. 지금까지의 소요시간 이것을 바탕으로 해당 경로가 가질 수 있는 최대값을 유추할 수 있다. 다음처럼 그래프를 그..