문제 풀이

[baekjoon 16434] 드래곤 앤 던전 (이분탐색 + 구현) (C++)

https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 용사가 던전을 지나가면서, 몬스터를 만나면 몬스터와 대결을 하고 체력 포션을 먹으면 회복이 되는 구현 문제이다. 이 과정을 진행할 수 있는 최소한의 hp를 구하는 문제다. 우선, 문제를 읽어보니 step의 n은 10만이었고, 체력의 MAX는 주어지지 않았다. 이 과정에서, 어떻게 최솟값을 구할지를 생각했다. x를 정해두고 매 단..

[baekjoon 13905] 세부 (이분탐색 + BFS) (C++)

https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 경로가 주어지고, 시작점 - 도착점까지 가는 경로의 가중치의 최솟값이 가장 큰 값을 구하는 문제이다. 예시 경로의 가중치가 4 - 2 - 4이면 이 경로의 최솟값은 2이다. 갈 수 있는 모든 경로 중 이 최솟값이 가장 큰 경우는? 처음엔 DFS + 백트래킹으로 모든 경로를 가면서, 최솟값을 저장했다. 하지만 시간 초과가 나왔다. 따라서 모든 경로를 가면서 ..

[baekjoon 1374] 강의실 (그리디, 우선순위 큐) (C++)

https://www.acmicpc.net/problem/1374 1374번: 강의실 첫째 줄에 강의의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄마다 세 개의 정수가 주어지는데, 순서대로 강의 번호, 강의 시작 시간, 강의 종료 시간을 의미한다. 강의 www.acmicpc.net 강의실의 이용 시작 시간, 종료 시간이 주어지고 이 예약 정보들을 감당하는 최소한의 강의실 개수를 구해야 한다. 처음엔, 누적 합처럼 모든 예약 시간을 배열에 저장한 다음에 겹치는 시간의 최대 개수를 구하려고 했지만 예약 시간의 범위가 10억이라서 불가능이라고 생각했다. 이 문제는 우선순위 큐를 이용해야 하는데, 이런 유형의 문제가 명확하게 생각하기 힘들어서 어렵다고 느껴진다. 1...

[baekjoon 14888] 연산자 끼워넣기(브루트포스, 백트래킹) (C++)

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 연산자가 주어지고, 해당 연산자들을 이용해서 만들 수 있는 최댓값과 최솟값을 구하는 문제다. 어느 연산자를 배치해서 최댓값이 나올 것이고, 최솟값이 나올 것이고 계산을 하긴 힘들다. 그리고 N의 개수는 최대 11이고 연산자의 개수는 최대 10개이므로 모든 경우의 수를 돌려서 찾아야 하는 문제이다. 1. DFS + 백트래킹을 이용해서 모든 경우..

[baekjoon 1939] 중량제한 (파라매트릭서치, BFS) (C++)

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 파라매트릭 서치와 BFS를 이용했던 문제로, 특정 무게를 버틸 수 있는 경로가 있는지 확인하는 문제였다. 고려해야 할 점은 다음과 같다. 1. 입력값으로 동일한 다리가 들어올 수 있다는 점 (1 2 4 / 1 2 7) 2. 가능한 중량의 최댓값을 골라야 하는데, 중량의 범위가 10억이라는 점 따라서, 중량 값을 먼저 정해두고 해당 중량 값..

[baekjoon 16926] 배열 돌리기 1 (구현) (C++)

https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 구현 문제를 잘 못 푸는 나에게 어려웠던 문제이다. 기본적인 배열 돌리기도 힘들어하다니.. 연습이 시급하다. 생각해볼 포인트는 두 가지이다. 1. 구현의 영역인 배열의 값을 한 칸씩 반시계 방향으로 옮기기 2. 사각형 모양의 배열들이 독립적으로 회전해야 하는 것 이런 식으로, 외곽 배열과 내부 배열은 독..