본문 바로가기

분류 전체보기702

[백준 1939] 중량제한 [Java] 풀이 출발지(from)와 목적지(to)에 대해 연결된 다리 중 최대중량을 구하는 문제다. 입력받은 다리의 중량제한에 대해 내림차순 정렬 후 순서대로 union시키며, from과 to가 동일한 집합에 속하는지(연결됬는지) 확인해주어 연결된 순간 union한 간선의 가중치가 최대 가중치이므로 출력하면 된다. 소스코드 소스코드 보기 출처 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 2023. 7. 9.
[백준 2206] 벽 부수고 이동하기 [Java] 풀이 (0, 0)에서 (N - 1, M - 1)까지 최대 벽을 1개 부수며 도착할 수 있는 최단거리를 구하면 되는 문제다. 하나의 2차원 배열에 최단거리를 기록하기에는 어느 순간 벽을 부술때와 부수지 않는 경우 중 어떤 경우가 더 빨리 도달할지 기록하기 어렵다. 때문에 두 경우에 대해 최단거리를 기록하고, 가장 먼저 (N - 1, M - 1)에 도달한 경우의 최단거리를 출력해주면 된다. 2차원 배열을 벽을 부수는 경우와 부수지 않는 경우로 하지 않고, queue에 넣어줄 때 현재의 최단거리를 가지고 있는 Point객체를 넣어주는 방식으로 풀이했다. bfs를 진행하며 다음 영역이 벽이 아니라면, 벽을 부순경우와 부수지 않은 경우 모두 아무 제한 없이 queue에 넣어주면 된다. 만약 다음 영역이 벽이라면,.. 2023. 7. 9.
[백준 21591] Laptop Sticker [Python] 풀이 노트북과 스티커의 너비를 입력받아서 스티커를 충분히 붙일 수 있는 공간이 있는지 확인하면 되는문제이다. 충분한 공간이 있기 위해서는 스티커보다 2cm씩 커야한다. 소스코드 소스코드 보기 출처 21591번: Laptop Sticker The single line of input contains four integers $w_c$, $h_c$, $w_s$ and $h_s$ ($1 \le w_c, h_c, w_s, h_s \le 1,000$), where $w_c$ is the width of your new laptop computer, $h_c$ is the height of your new laptop computer, $w_s$ is the width of the laptop s www.acmic.. 2023. 7. 7.
[백준 21633] Bank Transfer [Python] 풀이 이체할 돈의 액수에 따라 수수료가 얼마인지 계산해주는 문제다. 수수료는 돈의 액수(k)의 1%에 25 tugriks 을 더한 값이다. 단, 최소 100 tugriks 최대 2,000 tugriks라는 점에 유의하자. 소스코드 소스코드 보기 출처 21633번: Bank Transfer Tanya has an account in "Redgotts" bank. The bank has the commission to transfer money to "Bluegotts" bank that her friend Vanya has the account in. Tanya has read her bank rules and learned the following: The commission for the bank tr.. 2023. 7. 4.
[백준 10775] 공항 [Java] 풀이 Greedy 순서대로 들어오는 비행기에 대해 최대한 많은 비행기를 매칭시켜야 한다. 만약 순서대로 들어오는 비행기 중 한대가 매칭이 불가능 하다면 공항이 폐쇄되기 때문에 탐색을 중단해야 한다. 그렇다면, 비행기를 최대로 매칭시키는 방법은 뭘까? 비행기는 1 ~ g 번째 게이트 중 어디든지 도킹하면 된다. 하지만, 최대한 많은 비행기를 도킹하기 위해서는 g번 게이트에 가깝게 비행기를 도킹함으로써 다른 비행기가 확률적으로 도킹을 하게될 낮은 번호를 피하는 방법이다. 위의 그림을 보면 모든 비행기가 1 ~ gi번 게이트라는 선택지가 주어졌기에 최대한 높은번호를 선택해야 많은 비행기가 도킹 가능하다. 그렇다면 어떻게 최대한 높은 번호의 게이트를 찾을까? 단순한 방법으로 gi부터 1번 게이트까지 이미 도킹중.. 2023. 7. 4.
[백준 20040] 사이클 게임 [Java] 풀이 n개의 점에 대해 주어지는 m개의 선분이 사이클을 이루는지 확인하는 문제다. 쉽게 두 원소 x, y에 대해 union할 때 대표 원소가 동일하다면, 선형 구조상 동일한 집합에 속한 원소들이고 한 번 더 연결하려 시도했기 때문에 사이클을 형성할 것이다. 만약 union이 모두 정상적으로 이루어졌다면, 동일한 집합에 속한 원소들끼리 union이 이루어지지 않았기에 사이클은 생길 수 없다. 사이클이 생기지 않은 경우에는 0을 출력하면 된다. 소스코드 소스코드 보기 출처 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmic.. 2023. 7. 2.

티스토리툴바