DP27 [백준 02565] 전깃줄 [Java] 문제https://www.acmicpc.net/problem/2565풀이유명한 LIS 문제다.우선, 전깃줄의 위치 정보를 A 또는 B를 기준으로 정렬하자.A를 기준으로 정렬해보겠다.A에서 B로 가는 전깃줄이 교차하지 않도록 최소한의 전깃줄만 제거해야 한다.교차하지 않는 전깃줄들이 최대가 되기 위해서는 A에서 B로 향하는 전깃줄들이 최대한 촘촘히 위치가 증가해야 한다.즉 B의 LIS가 교차하지 않는 전깃줄의 수와 동일하다.문제에서 요구하는 정답은 제거해야 하는 전깃줄의 수 이므로 N에서 B의 LIS를 뺀 값을 출력하자.소스코드보기 2025. 2. 4. [프로그래머스] 등굣길 [Java] 문제https://school.programmers.co.kr/learn/courses/30/lessons/42898풀이MN크기의 보드에 장애물이 주어지고, (1, 1)에서 (M, N)까지 가는 최단 경로의 수를 1e9 + 7로 나눈 나머지를 출력하는 문제다.보통 좌표가 NM으로 주어지지만 여기서는 MN이다. puddles가 가지는 좌표또한 MN임을 유의하자.puddles에는 BLOCK표시를 해주자.( 0, 1 ) 또는 ( 1, 0 )에 1을 기입해 (1, 1)이 1을 가질 수 있도록 해주자.dp[i][j] : ( i, j )까지 오는 최단 경로의 수이후에는 모든 경로를 탐색하며 장애물이 없는 칸이라면 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]을 통해 최단 경로의 수를 합쳐주자.. 2025. 2. 1. [백준 01006] 습격자 초라기 [Java] 문제https://www.acmicpc.net/problem/1006풀이아마 문제 번호가 1006이거나, 알고리즘 분류에 DP밖에 없어서 많은 분들을 낚은(?) 문제입니다.평소 DP를 패턴을 찾아 푸시는 분들이라면 많이 어려울 수 있을 것 같습니다.우선, 특수소대가 구역을 침투하는 방법은 단순합니다.현재 영역과 인접한 영역의 합이 W보다 작다면 둘 다 점령 아니면 현재 영역만 점령하는 방식입니다. 이 문제는 다음과 같이 나눌 수 있습니다.선형 구조를 점령하기 위해 침투 시켜야 할 특구 소대의 최소 수 구하기원형 구조임을 고려해 초기값을 설정하고 다시 선형 구조를 점령하기주어진 영역을 원이 아닌 선형 구조로 표현하고,점령하는 경우의 수는 다음과 같이 3개의 상태로 표현할 수 있습니다.점화식에 대해서는 다음.. 2025. 1. 19. [백준 02533] 사회망 서비스(SNS) [Java] 문제https://www.acmicpc.net/problem/2533풀이우선, 주어지는 루트가 없으며, 어디서 탐색해도 상관없다.그래프를 구성 후 dfs를 진행하자. 얼리 어답터의 수가 최소가 되도록 만드는 방법에 대해 알아보자.맨 처음 리프노드는 자기 자신이 얼리 어답터라고 가정해야 한다.하지만, 부모 노드가 존재한다면 리프 노드는 얼리 어답터가 아닌 상태가 정답이다.여기서 dp는 두 상태(EARAY, GENERAL)에 대해 고려해야 한다.dp[i][j] : 상태가 i일때 j ~ N에 필요한 최소 얼리 어답터의 수dfs를 통해 방문을 진행하면 방문 표시와 함께 현재 정점이 얼리 어답터인 경우를 세주자.리프 노드까지 도달 후 리프 노드들이 얼리 어답터라고 표시된 후 부모 노드로 돌아와서 부모 노드의 두 .. 2025. 1. 17. [백준 02294] 동전 2 [Java] 문제https://www.acmicpc.net/problem/2294풀이N가지 종류의 동전이 주어질 때, 동전의 합이 K가 되는 최소 개수를 구하는 문제다.N은 최대 100이므로, 모든 동전에 대해 K를 만들어보는 경우를 전부 계산해볼 수 있다.dp[i] : 현재까지 살펴본 동전들로 i원을 만들기 위한 최소 개수우선 K의 최대는 10,000이므로 dp를 10,001, dp[0] = 0으로 초기화하자.이제 입력받은 동전에 대해 최소 동전 개수를 갱신하면 된다.범위 coin ~ K에 대해 현재 동전의 액수를 뺀 기록( dp[i - coin] )에 현재 동전 더하는 수가 적은 경우로 갱신해주면 된다. 만약 dp[K]가 초기값인 10,001이라면 K를 만드는 경우의 수가 존재하지 않는 경우이므로 -1을 출력하자.. 2025. 1. 6. [백준 01520] 내리막 길 [Java] 문제https://www.acmicpc.net/problem/1520풀이최대 500 X 500 크기의 보드에 대해 상하좌우 움직이면서 이전 위치보다 숫자가 작은 방향으로만 움직여 왼쪽 위에서 오른쪽 아래로 도착하는 경우의 수를 구하는 문제다.단순히 그래프 탐색으로 모든 경우의 수를 탐색하면 시간초과가 발생한다.중복 방문을 하지 않으면서도, 모든 경우의 수를 계산해야 한다.DP[i][j] = (i, j)에서 도착지 (M - 1, N - 1)까지 이동하는 경우의 수우선 입력을 받자.모든 지점이 도착지에 도달한다는 보장이 없으므로, dp는 -1로 초기화하자.dfs를 하며 만약 도착지에 도달했다면 1을. 이미 방문한 곳이라면 dp[x][y]를 반환해주자.그게 아니라면 새로운 탐색을 시작해야 하므로 dp[x][y.. 2025. 1. 4. 이전 1 2 3 4 5 다음
