본문 바로가기

문제 풀이19

[백준] 1509번 - 팰린드롬 분할 (Java) 문제 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 입력 출력 알고리즘 다이나믹 프로그래밍 주어진 문자열이 어디부터 어디까지가 팰린드롬인지 미리 기록을 해두고, 이를 이용해 팰린드롬 분할의 개수 최솟값을 갱신한다. 우선, 어디부터 어디까지가 팰린드롬인지 기록할 DP 테이블을 하나 만들어야한다. palandrom[i][j] : 문자열의 i번째 부터 j번째 까지가 팰린드롬인가? .. 2023. 12. 2.
[백준] 20136번 - 멀티탭 스케줄링 2 (Java) 문제 https://www.acmicpc.net/problem/20136 20136번: 멀티탭 스케줄링 2 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 알고리즘 그리디 알고리즘, 우선순위 큐 일단 기본적으로 문제 해결방법은 아래 "멀티탭 스케줄링" 1탄을 보고 와주길 바란다. 멀티탭 스케줄링 2는 1을 어떻게 더 효율적으로 해결할 수 있을지를 고민하면 되는 문제기 때문에 이에 대해서만 다룰 것이다. https://mclub4.tistory.com/3 [백준] 1700 - 멀티탭 스케줄링 (Java) 문제 https://www.acmi.. 2023. 12. 2.
[백준] 15586번 - MooTube (Gold) (Java) 문제 https://www.acmicpc.net/problem/15586 15586번: MooTube (Gold) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 알고리즘 오프라인 쿼리, 분리 집합 ( 추후 작성 예정 ) 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; publi.. 2023. 12. 2.
[백준] 1700 - 멀티탭 스케줄링 (Java) 문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 입력 출력 알고리즘 그리디 알고리즘 회의실 배정 문제와 유사하다. 멀티탭을 뽑는 횟수를 가장 최소화 할려면 현재 멀티탭에 꽂혀있는 것 중에서 가장 나중에 나오는 것을 뽑으면 된다. 예시로 멀티탭 구멍 개수가 2개이고 7개의 전자제품을 아래와 같이 사용한다면 2 3 2 3 1 2 7 우선, 처음에 나오는 2와 3은 멀티탭이 비어 있으므로 그냥 바로 꽂는다. 그 다음에 나오는 2와 3은 이미 멀.. 2023. 12. 2.
[백준] 20925번 - 메이플스토리 (Java) 문제 https://www.acmicpc.net/problem/20925 20925번: 메이플스토리 첫째 줄 사냥터 수 $N$ ($1 \le N \le 200$)과 방학 기간을 분 단위로 나타낸 $T$ ($1 \le T \le 1\,000$)가 주어진다. 다음 $N$개의 줄에는 $i$번째 사냥터의 특징인 입장에 필요한 최소 경험치 $c_i$와 $1$분마 www.acmicpc.net 입력 출력 알고리즘 다이나믹 프로그래밍 각 초마다 다른 곳으로 이동할지 아니면 계속 현재 사냥터에서 사냥하는게 더 유리할지 따져보고 dp 테이블을 갱신하면 된다. 이때, 각 던전별 입장 제한 경험치가 있으므로 사냥터를 이동할때는 이를 만족하는지 확인해줘야 한다. 또한, 던전과 던전을 이동할 때 이동 시간이 있으므로 시간내에 이.. 2023. 12. 2.

티스토리툴바