![]()
Problem Solution 1. 먼저 두 개의 정수 N과 K를 입력 받는다. 2. N 길이의 문자열을 입력받는다. 3. 각각의 'P' (사람) 위치에 대해 가장 가까운 햄버거('H')를 찾아서 먹을 수 있는지 확인한다. 4. for 루프를 통해 문자열을 순회하면서 'P' 위치를 찾고, 그 주변에 있는 햄버거 중에서 최대 K 거리 이내에 있는 햄버거를 찾아서 먹는다. 5. 햄버거를 먹었다면, 그 햄버거는 'E' (먹었다는 표시)로 표시되고, 더 이상 해당 햄버거를 먹을 수 없다. 6. 위의 과정을 모든 'P' 위치에 대해 반복하고, 햄버거를 먹은 사람의 수를 계산한다. 7. 최종적으로, 먹을 수 있는 햄버거를 먹은 사람의 수를 출력한다. Answer #include #include #include us..
![]()
문제 https://www.acmicpc.net/problem/20937 20937번: 떡국 Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외 www.acmicpc.net Algorithm "떡국 그릇 위에는 크기가 더 작은 떡국 그릇 하나를 쌓을 수 있다. 쌓은 떡국 그릇 위에 같은 방법으로 떡국 그릇을 또 쌓을 수 있다. 예를 들어, 크기가 4, 2, 3, 1인 떡국 그릇에 대해 4−3−2−1순서로 쌓을 수 있지만 3-4-2-1 순서로는 쌓을 수 없다. 이렇게 쌓은 한 개 이상의 떡국 그릇들을 떡국 그릇 탑이라고 하자." ..
문제 https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 풀이 문자열을 처음부터 끝까지 반복한다. 입력된 문자열에서 P를 찾는다. P일때 거리가 k이하인 H를 앞뒤로 찾는다. H가 없으면 다음 P로 넘어간다. 추가로 j가 0보다 작아지면 배열 시작 전의 요소를 찾고 있다는 뜻이므로 유효하지 않고, j가 n보다 크거나 같게 되면 배열 끝 너머의 요소를 찾고 있다는 뜻이므로 유효하지 않기에, j의 범위를 제한해준다. 이미 선택한 H는 다시 고르지 않..
![]()
풀이 상자를 높이와 너비순으로 정렬한다. -> 큰 상자부터 사용할 수 있어서 최소한의 상자를 사용할 가능성이 높아진다. 각 상자를 순서대로 확인하면서 해당 상자에 사탕을 담을 수 있는지 확인한다. 담을 수 있는 경우에는 해당 상자에 담고 candlesLeft에서 담은 사탕의 개수를 뺀다. 모든 상자를 확인하면서 담은 후, usedBoxes에는 사용한 상자의 개수가 저장된다. 마지막으로 useBoxes를 출력하여 최소한의 상자 개수를 표시한다. 코드 #include #include #include using namespace std; struct Box { int height; int width; }; bool compareBoxes(const Box &a, const Box &b) { return a.h..
https://www.acmicpc.net/problem/19941 19941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net # 문제 설명 문자열의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람(P)과 햄버거(H)의 위치가 문자열로 주어질 때, 햄버거를 먹을 수 있는 사람의 최대 수를 출력한다. # 문제 풀이 왼쪽부터 차례로 문자열을 읽어나갈 때, 왼쪽의 사람이 햄버거를 먹을 수 있는데 먹지 않는 경우, 손해가 발생한다. 따라서 왼쪽부터 읽어나가며 사람이 햄버거를 먹을 수 있는 경우의 수를 count 한다. 필자..
![]()
https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 알고리즘 유형 수학 그리디 알고리즘 비트마스킹 문제 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서..
![]()
https://www.acmicpc.net/problem/2852 2852번: NBA 농구 첫째 줄에 골이 들어간 횟수 N(1
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 / BFS 문제입니다. 우선순위 큐를 사용하기 위해 Comparable를 사용했고, bfs에서 초기 설정 및 현재 상태 처리를 담당하고, 범위 체크를 하는 함수를 만들어 문제를 해결했습니다. import java.util.*; import java.io.*; public class Main { static int dirX[] = {0, 0, -1, 1}; static ..
문제링크 https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 코드 import heapq input = __import__('sys').stdin.readline v,e,p = map(int,input().split()) graph = [[]*(v+1) for _ in range(v+1)] INF = float('inf') for _ in range(e): a,b,c = map(int,input(..
18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 단순 다익스트라 문제. 늘 풀던 것과는 다르게 거리정보 없이 그냥 1. graph리스트에 방향정보를 저장. dist리스트에 출발노드에서의 거리를 모두 저장 ~다익스트라 이용 : 힙큐모듈이용 q 리스트 생성. 출발노드 저장. dist에 출발노드는 거리 0 저장. while 반복문으로 q 끝날때까지 돌기! q에서 거리정보가장작은애 p..
문제 https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 풀이 도시의 개수만큼 다익스트라 계산하면 대략 10억번의 연산이 수행되어 시간초과가 나온다. 모든 도시에서 면접장으로 갈 수 있는 경로가 항상 있음 -> 면접장에서 도시로 향하는 다익스트라 가능 -> 도시의 연결 정보 입력 시 역방향으로 관계 지정해야 함. (도시: arr / 면접장: targets) 다익스트라에서 탐색 할 도시 리스트 ..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제풀이 위치가 X일 때 X-1 또는 X+1로 이동하거나 2*X의 위치로 순간이동할 경우 1초가 소모된다. 이동 방법은 3가지임을 알 수 있으며 동일한 시간이 소모됨을 확인할 수 있다. 각 방법에 대하여 시간이 1초가 소모되는 가중치가 동일한 상황이므로 너비 우선 탐색을 시행하여 최단 시간을 구한다. 현재 위치에서 각 방법으로 이동 한 결과를 큐에 넣은 ..
