본문 바로가기

백준5

백준 16118 - 달빛 여우 (다익스트라, 메모이제이션) 문제 링크: https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 문제 요약 달빛 여우와 달빛 늑대가 각자 다른 속도로 정점(그루터기)에 도달한다고 할 때, 달빛 여우가 달빛 늑대보다 정점에 먼저 도착하는 경우는 몇 가지인가? [문제 설명] 달빛 여우는 일정한 속도로 그루터기로 이동한다. 달빛 늑대는 홀수 번에는 달빛 여우의 두배 빠른 속도로, 짝수 번에는 달빛 여우의 2배 느린 속도로 이동한.. 2022. 7. 17.

백준 12908 - 텔레포트3 (다익스트라) 문제 링크: https://www.acmicpc.net/problem/12908 12908번: 텔레포트 3 첫째 줄에 xs와 ys가, 둘째 줄에 xe, ye가 주어진다. (0 ≤ xs, ys, xe, ye ≤ 1,000,000,000) 셋째 줄부터 세 개의 줄에는 텔레포트의 정보 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000,000) 입력으로 주 www.acmicpc.net 문제 요약 (xs, ys)의 위치에서 (xe, ye)로 가장 빠르게 갈 수 있는 시간을 구하시오. [문제 설명] (xs, ys): 출발위치 (수빈이의 위치) (xe, ye): 도착 위치 (집) 이동하는 두 가지 방법 점프: (x+1, y), (x-1, y), (x, y+1), (x, .. 2022. 7. 17.

백준 2467 - 용액 (이분탐색, 투포인터) 더보기 https://www.acmicpc.net/problem/2467 👆👆 더보기를 누르시면 문제 링크를 확인하실 수 있습니다. 문제 요약 - 산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어진다. - 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가까운 용액을 만들어 내는 두 용액을 출력하라. * 혼합한 용액의 특성값: 혼합에 사용된 각 용액의 특성값의 합 제한 조건 - 전체 용액의 수 (2≤ N ≤ 100,000) (100,000 가지 중 2가지 경우의 수를 찾으면 경우의 수가 상당히 많아져 1초만에 문제를 풀기에 무리가 있다.) - 용액의 특성 값 (-1,000,000,000 ≤ M ≤ 1,000,000,000) (Long 타입) 아이디어 - Two pointer (왼쪽 인덱스.. 2022. 4. 18.

백준 1477 - 휴게소 세우기 더보기 https://www.acmicpc.net/problem/1477 👆👆 더보기를 누르시면 문제 링크를 확인하실 수 있습니다. 문제 요약 - 다솜이는 현재 고속도로에 N 개의 휴게소를 가지고 있다. - 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. - 이미 휴게소가 있는 곳에는 휴게소를 세울 수 없다. - 휴게소는 정수 위치에만 세울 수 있다. Q. 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값의 최소를 구한다. ex. {200, 701, 800} 이 있을 때, 휴게소가 없는 구간의 길이는 {501, 101}이다. 이 중 최댓값을 501이다. 만약 휴게소를 1(M)개 더 지으려고 할 때, 이미 휴게소가 세워지지 않았다면 많은 후보가 생긴다. 451 에 세운다.. 2022. 4. 16.

백준 9205 - 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 👆👆 더보기를 누르시면 문제 링크를 확인하실 수 있습니다. 문제 요약 - 상근이와 친구들이 페스티벌에 간다. - 현재 위치에서 50m를 가기 전 한 병을 마시면서 간다. - 맥주는 20병을 넘을 수 없다. (20 * 50m = 1000m) (= 상근이가 갈 수 있는 최대 거리는 1000m(포함)다.) - 중간에 편의점에 들러 맥주를 살 수 있다. (= 편의점에 들를 수도 있고 들르지 않을 수도 있다.) Q. 상근이와 친구들이 행복하게 페스티벌에 도착하면 'happy'🥰 출력, 아니면 'sad'😥 출력 제한 조건 - 테스트 케이스 t (≤ 50) - 편의점 개수 n (≤ 100) - 상근이의 위치, 상점 위치, 페스티벌 도착 위치 x, y .. 2022. 4. 14.

이전 1 다음

티스토리툴바