목록DP (6)

갱스터하우스

[Java] 백준 2096.내려가기

➡️문제 링크https://www.acmicpc.net/problem/2096 💡아이디어DP현재의 선택은 이전의 선택의 영향을 받는 걸 보고 DP로 접근해야겠다고 생각했다. ✏️문제 풀이1. DP - 성공 처음에 DP 크기를 [N][N]로해서 메모리초과가 났다. 문제를 다시 읽어보니 N*3이어서 이 부분 수정하니 통과!import java.io.*;import java.util.*;/* * 현재 값은 이전값 영향 받음 -> dp로 접근해보자 * */public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new B..
코테 문제/백준 2026. 3. 10. 17:09
[Java] 백준 9465.스티커

➡️문제 링크https://www.acmicpc.net/problem/9465 💡아이디어dp 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 다시 생각해보면, 현재의 선택은 이전 선택의 영향을 받는다는 것이다. 어제 dp 문제를 풀며 알아챈 힌트가 이 문제에서도 보여서 dp로 접근해야겠다고 판단했다. ✏️문제 풀이1. dp - 성공점화식을 세우는데 조금 시간이 걸렸다단순하게 대각선을 선택하냐 마냐를 넘어 1열과 4열 두개만 선택하는 경우가 최댓값이라면, 그 사이 값들을 선택하지 않는 경우는 어떻게 선택하지? 이런 생각이 들었다.그래서 이 부분은 지피티의 도움을 받았다.우..
코테 문제/백준 2026. 2. 26. 14:39
[Java] 백준 11660.구간 합 구하기 5

➡️문제 링크https://www.acmicpc.net/problem/11660 💡아이디어누적합처음에는 M개의 좌표를 입력받을 때마다 하나하나 계산하려고 했는데매번 계산하는 것보다는 값을 미리 구해서 그때그때마다 그 값만 가져와서 쓰면 되지 않을까라는 생각이 들며누적합으로 접근해야 겠다고 생각했다. 처음에는 이렇게 더하는 줄 알고, 행을 기준으로 for문을 돌며 i == x1, i == x2, 그 외의 경우를 나누어 구했는데 틀렸다그래서 다시 읽어보니, 시작점은 y1, 끝점은 y2로 해서 구해야했다 ✏️문제 풀이1. 누적 합 - 성공 import java.io.*;import java.util.*;public class Main { static int N, M; static int [][] ..
코테 문제/백준 2026. 2. 25. 13:54
[Java] 백준 1932.정수 삼각형

➡️문제 링크https://www.acmicpc.net/problem/1932 💡아이디어DP ✏️문제 풀이1. DP - 성공 대각선 왼쪽은 (j-1), 대각선 오른쪽은 j로 설정해서현재 최댓값은 이전 라인의 대각선 왼쪽과 대각선 오른쪽 값 중 최댓값을 선택해 갱신하도록 했다처음에는 result값에 가장 꼭대기에 있는 값을 초기값으로 설정해야하나 고민하다본문에 있는 예제 테스트는 다 결과값이 나오길래 안 넣었는데 N = 1인 경우에는 틀려서 map[0][0]을 초기값으로 설정했다import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ // TODO A..
코테 문제/백준 2026. 2. 24. 18:06
[Java] 백준 1149.RGB거리

➡️문제 링크https://www.acmicpc.net/problem/1149 💡아이디어최솟값을 보고 BFS를 떠올렸다그러다 첫 번째 집부터, R, G, B 세가지 선택지가 있고앞에서 어떤걸 선택하냐에 따라 앞으로의 선택도 계속 달라지는데 BFS만으로 되나? 싶었고혹시 DP인가 싶다가 설마~ 이런생각으로 완탐으로 접근했다 ✏️문제 풀이1. 완전 탐색 - 오답(시간초과)이전에 선택한 색을 제외한 나머지 색을 고르면 계속 N번째까지 도는 방법으로 구현했다.문제에서 주어진 예제는 다 맞혔지만, 시간초과가 발생했다.import java.io.*;import java.util.*;public class Main { static int N; static int [][] cost; static int [] c..
코테 문제/백준 2026. 2. 24. 16:27
[이코테] 병사 배치하기(Python) / 백준 / 삼성SW 역량테스트

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 ..
코테 문제/이코테 2022. 10. 22. 11:29
이전 Prev 1 Next 다음