Coding Test/BOJ

[BOJ/JAVA] 12764번: 싸지방에 간 준하

12764번: 싸지방에 간 준하현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.https://www.acmicpc.net/problem/12764키워드모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수자리별로 몇 명의 사람이 사용했는가구현중요한 것은 우선순위 큐를 이용하여 가장 시간이 짧은 자리를 찾아가면 안된다는 것이다.예외가 발생하는 경우현재..

[BOJ/JAVA] 1374번: 강의실

1374번: 강의실첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 번호는 1부터 N까지 붙어 있으며, 입력에서 꼭 순서대로 주어지지 않을 수 있으나 한 번씩만 주어진다.https://www.acmicpc.net/problem/1374키워드최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.구현우선 순위 큐를 이용하여 구현한다.static class Lecturenumber강의 번호startTime강의 시작 시각endTime강의 종료 시각lectureClassQueue강의가 끝나는 시각의 오름차순 정렬 강의 데이터를 강의 시작..

[BOJ/JAVA] 7662번: 이중 우선순위 큐

7662번: 이중 우선순위 큐이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다.https://www.acmicpc.net/problem/7662키워드데이터를 삽입하는 연산데이터를 삭제하는 연산은 또 두 가지로 구분우선순위가 가장 높은 것을 삭제우선순위가 가장 낮은 것을 삭제Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q..

[BOJ/JAVA] 1781번: 컵라면

1781번: 컵라면상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다. 위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.https://www.acmicpc.net/problem/1781키워드문제를 푸는데는 단위 시간 1각 문제의 데드라인은 N이하의 자연수이다.각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231 보다 작거나 같은 자연수 구현잘못된 접근 방법데드라인의 오름차, 컵라면 수의 내림차순으로 정렬한..

[BOJ/JAVA] 1459번: 걷기

생성 일시: 2022년 12월 11일 오후 9:52 태그: Java 1459번: 걷기 1459번: 걷기 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 ( www.acmicpc.net 키워드 세준이는 현재 (0, 0)에 있다. 그리고 (X, Y)에 위치한 집으로 가려고 한다. 세준이가 걸을 수 있는 방법은 두가지 인데, 하나는 도로를 따라서 가로나 세로로 한 블록 움직여서 이번 사거리에서 저 사거리로 움직이는 방법 블록을 대각선으로 가로지르는 방법이 있다. 구현 대각선 비용이 이득인 경우 대각선 이동 비용 < 가로세로 이동 비용 * 2 최대한 대각선으로 이..

[BOJ/JAVA] 21758번: 꿀 따기

태그: Java 21758번: 꿀 따기 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 키워드 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.) 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다. 구현 꿀의 누적합을 구한다. 3가지 경우의 수가 생긴다. 꿀통이 0에 있는 경우 어처피 n-1은 못먹으므로, 하나는 무조건 한쪽 끝에 두는 것이 이득이다. 나머지는 전부 돌아가며 최댓값을 찾는다. 꿀통이 n-1에 있는 경우 어처피 0은 못먹으므로, 하나는 무조건 한 쪽 끝에 두는 것이 이득이다. 나머지는 전부 돌아가며 최댓값을 찾는다. 꿀통이 중간에 있는 경우 벌을 양 쪽 끝에 두는 것이 이득이..

[BOJ/JAVA] 2036번: 수열의 점수

태그: Java 2036번: 수열의 점수 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net 키워드 한 정수를 제거하는 경우에는 그 정수가 점수가 되고 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대 구현 양이아닌 정수의 경우 작은 것 끼리 최대한 곱하는 것이 이득이다. 양의 정수의 경우 큰 것 끼리 최대한 곱하는 것이 이득이다. 단, 1의 경우 더하는 것이 이득이다. 코드 import java.io.BufferedReader..

[BOJ/JAVA] 1783번: 병든 나이트

태그: Java 1783번: 병든 나이트 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 키워드 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제..

[BOJ/JAVA] 14613번: 너의 티어는?

14613번: 너의 티어는? 14613번: 너의 티어는? 규환이는 최근에 오버워치에 흠뻑 빠졌다. 그의 랭크 점수는 현재 2000점이며, 그는 오늘 랭크게임을 20번 할 예정이다. 규환이는 게임을 시작하기 전 자신의 그동안 승률을 통해 자신이 브론즈, www.acmicpc.net 키워드 그의 랭크 점수는 현재 2000점이며, 그는 오늘 랭크게임을 20번 할 예정이다. 게임을 이길 경우 얻는 포인트는 50 Point, 질 경우 잃는 포인트도 50 Point, 비길 경우 Point의 변화는 없다. 브론즈: 1000~1499 실버: 1500~1999 골드: 2000~2499 플래티넘: 2500~2999 다이아: 3000~3499 구현 랭크 점수는 2000이지만 배열 크기의 압축을 위해 1000점씩 깎아서 계산..

[BOJ/JAVA] 1005번: ACM Craft

1005번: ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 키워드 모든 경기에서 특정 건물만 짓는다면 무조건 게임에서 이길 수 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 특정건물을 가장 빨리 지을 때까지 걸리는 최소시간을 알아내는 프로그램 구현 i 건물을 짓는데 필요한 선행 건물의 인접리스트를 구현한다. 위 그림에서 4번 건물을 짓기 위해서 2, 3의 건물 인덱스를 삽입한다. 2, 3건물도 마찬..