본문 바로가기

ALGORITHM

 (212)
백준 15565 귀여운 라이언 (Java) 1. 문제 링크 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 라이언이 K개 이상 포함되는 범위의 크기를 위해 투포인터로 구했다. 2. K개가 될때까지 오른쪽으로 늘리는데, 오른쪽에 라이언이 오면 추가하고, K개 이상이 되면 넘어간다. 3. K개의 경우, 최솟값이 되는지 확인한다. 4. 다음으로 넘길 때, 제일 왼쪽이 라이언일 경우 1을 뺀다. 4. 코드 import java.io.BufferedReader; import java.io.IOException;..
백준 13335 트럭 (Java) 1. 문제 링크 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 트럭 큐에 각 트럭의 무게를 저장한다. 2. 다리의 각 위치마다 트럭 무게를 넣는 큐를 만든다. 2-1. 처음에는 다리에 아무 트럭이 없기 때문에 모든 위치에 0을 넣는다. 3. 시간이 지나면서 다리 위치를 옮기기 위해 다리 큐에서 하나를 뺀다. 4. 지나올 트럭이 남아있으면 최대 하중을 확인한다. 4-1. 지금 순서의 트럭이 추가되어도 최대 하중을 넘지..
백준 1939 중량제한 (Java) 1. 문제 링크 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 2. 문제 및 입출력예제 3. 문제 풀이 1. 최대 중량을 넘지 않는 최댓값을 찾아야 한다. 2. 두 섬을 연결시켜야 해서 BFS 탐색을 이용했고, 시간 초과를 생각해 이분 탐색을 함께 이용했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja..
백준 2056 작업 (Java) 1. 문제 링크 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 위상정렬을 이용하여 문제를 풀었다. 2. 선행되는 작업을 먼저 처리한 후, 진입 차수가 0이 되면 큐에 넣어 작업이 되도록 했다. 3. dp를 이용하여 지금까지 누적 + 다음 노드의 시간 vs 다음의 누적 중 큰 값을 저장했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..
백준 2831 댄스 파티 (Java) 1. 문제 링크 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 키가 작은 여자와 키가 큰 여자, 키가 작은 남자와 키가 큰 여자로 나누어서 저장한다. 2. 전부 정렬한다. 3. 여자와 남자 각각 인덱스 번호를 가지고, 조건이 성립하는 경우에만 커플의 수를 증가한다. 4. 그 외에는 조건에 맞을 때까지 키가 커야 하는 조건의 사람이 커질 때까지 인덱스 번호를 증가한다. 4. 코드 import java.io.BufferedReader; import java.io..
백준 15684 사다리 조작 (Java) 1. 문제 링크 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 사다리의 연결된 가로선으로 (1) - (-1)로 저장해 연결 여부를 판단했다. 2. 가로선을 1, 2, 3개 추가한 순서로 dfs를 진행했다. 3. 선을 하나씩 추가하는데 3개가 넘지 않도록 하면서, 다른 가로선과 연결되지 않게 했다. 4. 한 가로선을 추가할 때마다 i번이 i번에 도착하는지 확인하고, 다른 사다리에 영향을 끼치지 않도록 다시 뺐다. 4. 코드 import java.io.Buffere..
백준 2623 음악프로그램 (Java) 1. 문제 링크 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. PD의 수만큼 ArrayList를 만든다. 2. 입력받은 순서대로 list에 넣으면서 진입차수를 더해준다. 3. 위상정렬을 진행한다. 3-1. 처음에 진입차수가 0인(선행되는 수가 없는) 숫자를 큐에 넣는다. 3-2. 큐에서 빼고 결과 list에 추가한다. 3-3. 그 수와 연결된 숫자들의 진입차수를 하나씩 빼면서 0이 될 때 큐에 넣는다. 4. 위상 정렬이 끝난 후 결과 list..
백준 14226 이모티콘 (Java) 1. 문제 링크 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 최소 시간을 구하는 문제라 BFS 탐색을 이용했다. 2. 큐에 지금 이모티콘 수(now), 클립보드에 있는 이모티콘 수(save), 연산 횟수(cnt) 3가지를 넣는다. 3. 원하는 이모티콘 수가 나올 때까지 반복한다. 3-1. now가 0보가 크고, [now][now]에 방문한 적이 없는 경우에, 클립보드로 복사한다. 3-2. save가 0보다 크고, now+save가 2000보다 작고, [now+sa..

티스토리툴바