코딩테스트 기록 8일차

코딩테스트 기록 7일차

1. 1697번: 숨바꼭질 (메모리: 23224KB, 시간: 168ms)

Problem Link
Solved Link

문제 정리

• 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.
• X-1 or X+1, 2*X만큼 이동할 수 있다.
• 수빈이와 동생의 위치가 주어졌을때, 수빈이가 동생을 찾을 수 있는 최소 시간을 구하라.

개념 및 접근법

• BFS 사용

2. 13975번: 파일 합치기 3 (메모리: 280956KB , 시간: 2992ms)

Problem Link
Solved Link

문제 정리

• 소설가 김대전은 소설의 각 장을 다른 파일에 저장하고, 최종적으로 하나의 파일로 합친다.
• 두 파일을 합칠 때는, 두 파일의 크기의 합만큼 비용이 발생한다.
• 모든 장을 하나의 파일로 합칠 때 필요한 최소 비용을 계산하라.

개념 및 접근법

• 우선순위 큐를 사용해 가장 작은 크기의 파일을 합쳐나가는 방식으로 접근해본다.
• 양의 정수 K (3 ≤ K ≤ 1,000,000), 하나의 파일 크기는 10000을 초과하지않는다.

3. 1863번: 스카이라인 쉬운거 (메모리: 19832KB, 시간: 212ms)

Problem Link
Solved Link

문제 정리

• 스카이라인의 지점 개수 n이 주어진다. (1 ≤ n ≤ 50,000)
• 스카이라인의 고도가 변하는 지점의 x, y 좌표가 주어진다. (1 ≤ x ≤ 1,000,000, 0 ≤ y ≤ 500,000)
• 첫번째 지점의 x 좌표는 항상 1이다.
• 스카이라인을 통해 건물이 최소 몇채인지 추정한다.

개념 및 접근법

• 건물높이 문제이니 Stack사용(건물높이 문제면 Stack쓰는거에 의문점이 들기시작함)
• 높이만으로 비교해서 충분히 비교가능.
• 높이가 갱신되면 빌딩이 있는것으로 판단

4. 1939번: 중량제한 (메모리: 69448KB, 시간: 612ms)

Problem Link
Solved Link

문제 정리

• N개의 섬과 이들을 연결하는 M개의 다리가 있는 나라가 있으며, 두 공장이 위치한 섬 끼리 수송할 수 있는 물품의 최대 중량을 구하기
• 섬의 수(2 ≤ N ≤ 10,000), 다리의 수(1 ≤ M ≤ 100,000)이며, 각 다리는 중량 제한 C(1 ≤ C ≤ 1,000,000,000)를 가진다.

개념 및 접근법

• 모든 다리는 양방향이다. (양방향 그래프 사용)
• 이진탐색으로 중량 제한을 효과적으로 잡아간다(범위가 너무크기떄문)
• 단순 이진탐색으로만으로는 못풀기때문에, BFS를 활용해서 이진탐색의 mid값을 기준으로 섬에 도달가능한지 여부를 판단하는 로직을 작성한다.