dp

https://www.acmicpc.net/problem/30461문제 요약N * M 의 공간이 존재하고, 각 칸에는 물고기 여럿이 존재가방 먼 칸은 (N, M)무게가 a인 무게추를 매달아 b만큼 힘으로 던지면 (a,b)칸에 미끼가 존재이때, (a,b)에 존재하는 미끼는 1 ≤ i ≤ a인 모든 정수 i에 대해서 (i,b)에 존재하는 모든 물고리를 사로 잡는다.만약 낚싯줄을 한 바퀴 감아 올리면, (a,b)에 위치한 미끼는 (a-1,b-1)로 이동하고, 이동한위치에서 물고기를 사로잡는다.이때, 무게추의 무게와 낚싯대를 휘두를 힘을 알려줄 때마다, 낚싯대를 휘두른 뒤 회수할 때까지 낚싯줄을 감아올리면 몇 마리의 물고기가 사로잡힐지 구해라시간 제한2초입력일감호의 크기를 나타내는 정수 N, M과 낚싯대를 휘두..

https://www.acmicpc.net/problem/2662문제 요약만원 단위로 각 기업에 투자할 수 있다돈을 투자하게 되면 얻게되는 이익도 있다.투자액이 정해져 있고, 기업의 개수와 각 기업에 투자했을 때 얻는 이익이 주어질 때, 가장 많이 얻을 수 있는 투자방식과 그때의 이익금을 구하라시간 제한1초입력투자 금액 N과 투자 가능한 기업들 개수 M1 ≤ N ≤ 300, 1 ≤ M ≤ 20N개의 줄에 투자액수와 각 기업이 투자가에게 주는 이익이 주어진다.투자 금액은 항상 1~N같은 투자금액이 두 번이상 주어지지 X ⇒ i번째 줄에 주어지는 투자 금액은 i-1만원출력얻을 수 있는 최대 이익 출력각 기업에 투자한 액수 출력접근법재귀DP로 접근했고, 매개 변수로 현재 갖고 있는 금액 remain과 현재 가..

알고리즘 문제) BOJ 14923. 미로탈출 링크 : https://www.acmicpc.net/problem/14923문제 요약N*M 미로가 존재출발위치는 (Hx,Hy)이며, 미로 탈출 위치는 (Ex, Ey)이다미로에는 벽이 존재하며, 통과가 불가능하다그러나, 한번 마법을 부리면 벽을 허물 수 있다미로를 탈출 할 수 있는지 알아보고, 가능하다면 최단 경로 D를 출력해라시간 제한1초입력미로 크기 N * M2 ≤ N ≤ 10002 ≤ M ≤ 10001 ≤ Hx, Hy, Ex, Ey ≤ 1000출발위치랑 탈출위치는 다름행렬 정보가 주어짐다0 : 빈공간1 : 벽출력최단 경로 D 출력해라탈출 할 수 없다면 -1출력접근법최단 경로 알고리즘 BFS를 사용해 접근BFS를 돌리며 방문체크 할 때, 현재 마법을 썼는냐,..

알고리즘 문제) BOJ 5944. Apple Delivery 링크 : https://www.acmicpc.net/problem/5944문제 요약C개의 길과 P개의 목초지가 존재이때, 각 길에는 거리비용이 존재PB에서 시작해 PA1와 PA2 목초지로 방문하려고 할 때, 이동해야할 최소 거리는?시간 제한2초입력C, P, PB, PA1, PA21 ≤ C ≤ 20만1 ≤ P ≤ 10만모든 거리의 합은 20억을 초과XC개의 줄에 두 목초지 번호와 그 사이 거리가 주어짐출력두 목초지를 방문할 때 이동할 최소 거리는?접근법PB에서 PA1과 PA2 방문을 위한 최소 경로를 구해야하므로 총 2가지 경로가 있을 수 있다PB → PA1 → PA2PB → PA2 → PA1따라서, PB ~ PA1 / PB ~ PA2 / PA1..

알고리즘 문제) BOJ 3258. 컴포트 링크 : https://www.acmicpc.net/problem/3258문제 요약1에서 게임을 시작해서, Z번째 필드에 도착하는 것이 이 게임의 목표도착점은 K만큼씩 시계방향으로 이동해 도달해야 한다도착점으로 가는 길에 장애물이 있는 필드를 밟아서는 안 된다예를들어 N=13, K=3 그리고 Z=9라고 했을 때 아람이는 1,4,7,10,13,3,6 그리고 9 의 필드를 지나게 된다게임판의 정보가 주어졌을 때 도착점에 도착할 수 있는 가장 작은 K를 찾는 프로그램을 작성시간 제한1초입력첫째 줄에는 N(2 ≤ N ≤ 1000), Z(2 ≤ Z), M(0 ≤ M ≤ N-2)N은 필드의 수이고 Z는 도착해야하는 필드의 번호를 의미다음 줄에 M개의 서로 다른 정수정수는 장..

알고리즘 문제) BOJ 16469. 소년 점프 링크 : https://www.acmicpc.net/problem/16469문제 요약마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다.뒤늦게 미로에 도착한 악당 무리 3명는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다.악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다.또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다.악당은 서로 다른 지점에서 마미손을 찾기 시작하는데 이들은 세 명이 한 지점에서 모였을 때 걸린 시간이 최소가 되는 지점에 마미손이 숨어있다고 확신R*C 크기의 미로가 주어지고, 악당들의 시작 위치가 주어질 때, 한 지점에 세 악당이 모일 때 걸린 시간이 최소가 ..

알고리즘 문제) BOJ 14725. 개미굴 링크 : https://www.acmicpc.net/problem/14725문제 요약로봇 개미로부터 얻은 개미굴 저장소를 바탕으로, 개미굴 구조를 출력해라예를들어, 아래와 같은 정보를 받았다면KIWI BANANAKIWI APPLEAPPLE APPLEAPPLE BANANA KIWI아래처럼 출력해라 APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA개미굴의 각 층은 "--" 로 구분하며, 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다시간 제한1초입력첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개두 번째 줄부터 N+1 번째 ..

알고리즘 문제) BOJ 13398. 연속합 2 링크 : https://www.acmicpc.net/problem/13398문제 요약n개의 정수로 이루어진 임의의 수열이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다수는 한 개 이상 선택해야 한다수열에서 수를 하나 제거할 수 있다시간 제한2초입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수출력첫째 줄에 답을 출력접근법부분 연속 수열의 합 중 가장 큰 값을 구하는 문제이때, 중간에 하나 제거가 가능함매개변수 start, end를 통해 부분 연속 수열이 시작됐는지, 끝나는지 체크하도록 했다0 :..

알고리즘 문제) BOJ 1727. 커플 만들기 링크 : https://www.acmicpc.net/problem/1727문제 요약여자친구가 없는 남자 n명과 남자친구가 없는 여자 m명각 사람의 성격은 어떤 정수로 표시최대한 많은 커플을 만들고, 각 커플을 이루는 두 사람의 성격의 차이의 합이 최소가 되도록 하자시간 제한2초입력첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)다음 줄에는 n명의 남자들의 성격그 다음 줄에는 m명의 여자들의 성격성격은 1,000,000이하의 자연수출력성격의 차이의 합의 최솟값을 출력접근법그리디 + dp로 풀어야 한다.최대한의 커플을 만들면서, 커플들의 성격차 합이 최소가 되게 해야함최대한의 커플을 만든다 == min(남학우 수, 여학우 수)만큼 만들어져야 함또한, 각 성별의..

알고리즘 문제) BOJ 4179. 불! 링크 : https://www.acmicpc.net/problem/4179문제 요약지훈이가 불에서 타기 전에 얼마나 빨리 탈출할 수 있는지 판단하기불은 매 분마다 한칸씩 수평, 수직으로 이동(네방향 확산)지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다지훈이와 불은 벽을 통과할 수 없다시간 제한1초입력R C1 ≤ R,C ≤ 1000행, 열R개의 줄에 맵이 주어짐‘#’ : 벽‘.’ : 빈칸‘J’ : 지훈이 초기 위치‘F’ : 블이 난 공간J는 입력에서 하나만 주어진다.출력지훈이가 미로를 탈출 할 수 없다면 IMPOSSIBLE가능하다면, 가장 빠른 탈출 시간 출력접근법bfs 알고리즘 사용우선 지훈이가 이동 가능한 경우는 여러 케이스가 있다큐에 bfs를 돌며 이동..