https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 정말 미세하게 DP에 대한 감이 잡히기 시작한 것 같다. DP문제라는 것을 알고 풀긴 했지만! 점화식을 찾아냈다는 것이 뿌듯했다. 하지만 점화식을 찾아낸 것 그뿐이고 그다음을 어떻게 해야 할지 몰라 답을 찾아서 봤다....ㅎ 풀이 먼저 점화식을 찾아낸 방법은 하나하나 다 써봤다. 이것만큼 좋은 게 있을까? $$\Large d[i] \space =\space d[i-1] \space + \space d[i-2]..

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 진짜 너 어어어ㅓㅇ무 어려웠다 답을 보면서도 이게 왜? 대체 왜? 라는 생각이 끊이질 않았다. 이러한 문제를 KnapSack Problem(배낭 채우기 문제)라고 말한다. 풀이 일단 다이나믹 프로그래밍을 사용해서 풀어야 된다. (진짜 정말 어떻게 이걸 다이내믹 프로그래밍으로 테이블을 정의해서 풀어낼 생각을 한 걸까? 미친 걸까? 대..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 일단 예전에 풀었던 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 사용하는 것이라는 건 자명한 사실! 하지만 여기선 추가 된것이 있었으니, 그 경로까지 구해야 하는 것이다. 이슈다 응용은 못한다.... 일단 당연히 문제에 대해 고민을 해보고 답을 봤다. 풀이 아이디어 가장 긴 배열을 구하며 경로도 추가 적으로 pr..

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 진짜 정말..... 너무 어려웠다 답을 봐도 왜 이렇게 풀었는지를 몰라 계속 봤고 지금은 조금 이해한 상태다 DP 진짜 너무 어렵다.... 에효.... 아이디어 먼저 몇 가지 가능성을 보도록 하자 1. 현재 나의 위치에 자두가 떨어진다 a. 가만히 있고 자두를 잡는다 2. 현재 나와 다른 위치에 자두가 떨어진다 a. 다른 나무로 이동하여 자두를 잡는다 b. 가만히 있으며, 떨어지는 것을 지켜본다 코드로 구..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 아이디어 1. 미세먼지를 확산시킨다 2. 공기청정기가 돌아간다 3. T번만큼 반복한다 일단 공기청정기를 반시계, 시계 방향으로 돌리는 법을 생각해야 했다. 공기청정기 돌리기 공기청정기의 머리 쪽은 반시계 방향, 몸통 쪽은 시계방향이다. 이렇게 둘로 나눠서 구현했다. 벽을 만날 때까지 반복해야 하니 방향이 필요하다 어느 방향으로 벽을 만날 때까지 나아갈 것인지 int dx[4] = {-1,0,1,..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 나에게는 정말 어려웠던 문제다 1시간 정도 고민하고 감도 잡히질 않아 답을 보았다. 풀이 배열 두 개를 만든다. 원본 배열, 테이블이다. int arr[1005]; int dp[1005]; 답에서는 한 번씩 다 돌아가면서 체크하는 방식을 알려줬다. 그림으로 설명해보겠다 이중 for문을 사용하여 i에 대하여 나보다 작은 수이면 더하고 본다..

첫 번째 아이디어 일단 기본적인 재귀 형태로 풀려고 시도했다. 당연히 안될 걸 알고 있었지만 일단 시도 했으며 결과는 당연히 메모리 초과 CODE //Moo 게임 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } //횟수 int n; int tot = 0; bool isFine = false; void isMoo(bool m2o){ //true = m, false = o if(m2o && tot == n){ cout n; moo(n/2); return 0; } 이렇게 해본 후 문제점이 뭔지를 찾아 나갔다. 1. 재귀를 몇번 반복해야 하는 가를 알려줘야 한다. 2. 그저 ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 시행 착오 최근에 다이나믹 프로그래밍 문제를 풀때 테이블이나 재귀식이 새각나지 않는 다면 브루트 포스 또는 모든 것을 다 검사하는 방식으로 코드를 짜보고 거기서 추가 적으로 재귀를 짜라는 식의 설명을 들은 적이 있다. 그리하여 나는 일단 DFS를 사용하여 모든 경우의 수를 다 구하였으며, 결과는 시간 초과 였으며 당연한 결과라 생각해 다이내믹 프로그래밍으로 짜보려고 노력했다. CODE #include using namespace std; void init(){ ios_..

요약 1. 3으로 나누어 떨어지면 3으로 나누거나 2. 2로 나누어 떨어지면 2로 나누거나 3. 1을 빼거나 해서 4. 어떻게 해야 가장 빨리, 입력받은 N을 1로 만들 수 있는가? 아이디어 들어가기에 앞서 나의 첫 다이나믹 프로그래밍 문제이다. 답을 보고 풀었다. 강의에서는 먼저 테이블을 정의한다음 점화식을 찾았다. 테이블 정의 이 문제의 테이블은 D[i] = i 각 숫자에 대응되는 인덱스를 테이블로 만들 수 있을 것 같다 점화식 d[12] = d[12/4], d[12/2], d[12-1] d[3] = d[3/3], d[3-1] d[6] = d[6/3], d[6/2], d[6-1] d[11] = d[11-1] 이런식으로 점화식을 만들 수 있을 것 같다. 하지만 나 혼자 풀어 볼 때 무조건 재귀를 쓰겠지..

https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 요약 1. 현재 나의 위치와 탈출가능한 위치가 있다 2. 벽을 딱 한번 부술 수 있다. 벽을 부수고 최단 경로를 구하는 것 아이디어 예전에 비슷한 문제를 풀었던 적이 있다. 벽을 부순 상태일 때의 배열을 따로 만드는 방법으로 풀었던 기억이 있다. 그것과 비슷하게 dist [n][m][2]라는 배열을 만들고 dist[a][b][0] // 벽을 부수지 않은 상태 dist[a][b][..