김머성 블로그

[BAE/<JOON> 문제풀이] 1520. 내리막길 (DP.032)

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net 어려운 문제는 dfs가 항상 섞여들어가는 것 같다. 이 문제는 다른 블로그의 풀이를 참고하여 풀었다. 일단 점화식 도출까지는 간단하게 생각해 낼 수 있다. 경찰차와 비슷하게 bottom-up 방식으로 호출을 하다가 이미 값을 가지고 있는 노드를 탐색하면 해당 값을 반환해가며 합을 구하내가는 방식이다. 하지만 ..

[BAE/<JOON> 문제풀이] 1904. 01타일 (DP.031)

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 더보기 #include #include using namespace std; int main() { vector dp; int n; ci..

[BAE/<JOON> 문제풀이] 11054. 가장 긴 바이토닉 부분 수열 (DP.030)

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 최장 증가 부분 수열을 앞뒤로 찾아서 합쳤을 때 가장 큰 위치를 찾아 -1 하면 된다. (2개 수열에 현재 위치 숫자가 2번들어가므로) 더보기 #include #include using namespace std; int main() { int n; vector arr; vector dp1, dp2; cin >> n; arr.resize(n + 1); dp1.resize(n + 1); dp2.resize(n + 2);..

[BAE/<JOON> 문제풀이] 가장 긴 감소하는 부분 수열 (DP.029)

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다. www.acmicpc.net 더보기 #include #include using namespace std; int main() { int n; vector arr; vector dp; cin >> n; arr.resize(n + 1); dp.resize(n + 1); for (int i = 1; i > arr[i]; dp[i] =..

[BAE/<JOON> 문제풀이] 2133. 타일 채우기 (DP.028)

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net 5항까지 수기계산하고 규칙찾는데 규칙이 5~6개는 나왔다. 6항부터는 수기계산이 힘들어서 그냥 채점 박치기 했다. 이런거 대회문제에 나오면 시간 진짜 많이 잡아먹힐거 같다. 더보기 #include #include using namespace std; int main() { int n; cin >> n; i..

[BAE/<JOON> 문제풀이] 2618. 경찰차 (DP.027)

https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이 www.acmicpc.net 각각의 사건을 해결 할 때마다 고려해야할 최저수치는 다음과 같다. 현재 사건을 n번째 사건이라고 할 때 [n-1번 째 사건을 다른 경찰이 해..