Coding Test/BaekJoon

문제https://www.acmicpc.net/problem/2839 접근법우리가 거스름돈을 줄 때 최소 개수로 주기 위해서는 큰 단위 순으로 계산을 하면 된다. 예를 들어 12,530원을 거슬러줘야 하는 상황일 때 큰 단위 순으로 10,000원 2개, 1,000원 2개, 100원 5개, 10원 3개 이런 식으로 계산한다는 뜻이다.이 문제도 비슷한 맥락으로 생각해보면 5kg으로 최대한 가져간 후, 남은 무게를 3kg으로 가져가면 된다. 이때 주의할 점은 5kg로 최대한 가져간 후 남은 무게가 3의 배수가 아닐 경우 3kg으로 남은 무게를 전부 배달할 수 없다는 것이다. 따라서 남은 무게가 최소한의 3의 배수가 될 때까지 5kg으로 배달하고 나머지는 3kg으로 배달해야 한다. 풀이javaimport jav..

문제https://www.acmicpc.net/problem/11000 접근법문제를 처음 봤을 땐 먼저 수업을 정렬해야겠다고 생각했다.시작 시간 순으로 정렬을 한 뒤, 현재 수업이 들어갈 강의실을 찾으면 된다.현재 수업이 들어갈 강의실은 앞 수업들의 종료 시간을 비교하면 된다. 현재 사용 중인 강의실들의 종료 시간을 저장한다.저장된 강의실의 종료 시간 중 가장 먼저 끝나는 강의실과 현재 수업의 시작 시간을 비교해 해당 강의실을 사용할지, 추가로 강의실을 사용할지 결정한다. 왜 가장 먼저 끝나는 강의실만 비교하면 될까?가장 먼저 끝나는 강의실을 현재 수업에서 사용할 수 없다면 더 늦게 끝나는 강의실 역시 사용할 수 없기 때문이다 코드import java.io.BufferedReader;import java..

문제https://www.acmicpc.net/problem/1753 1753번: 최단경로첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가www.acmicpc.net 접근법다익스트라 알고리즘을 이해하는 문제이다. '시작점에서 다른 모든 정점', '간선의 가중치가 모두 양수' 라는 점에서 다익스트라로 푸는 문제임을 알아차려야 된다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util...

문제https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net 접근법DP 기본 문제이다. i번째 포도주를 마실 순서라고 할 때, 내 앞에서 연속으로 2잔을 마신 경우는 제외해야 하므로 ①DP[i - 2] ② DP[i - 3] + wine[i - 1] 중 큰 값을 찾아야 한다. 여기서 주의할 점은, i번째 포도주를 안 마시는 경우가 존재할 수 있으므로 아래와 같이 점화식을 작성해야 한다.DP[i] = i번째 포도주를 마실 순서일 때, 마신 누적 포도주 양의 최댓..

문제https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커www.acmicpc.net 접근법문제를 이해하는 데 시간이 많이 걸렸다.이 직선을 시계 방향으로 90도 회전하면 ↓ 이고, 이걸 끝 점에 붙이면 아래와 같은 드래곤 커브가 생긴다고 이해해서 문제가 도통 이해가 되질 않았다. 그래서 예제 1번에 있는 3개의 드래곤 커브 중, 3세대까지 진행되는 2번째 예시를 가지고 규칙을 찾아냈다. 문제 하단에 힌트로 그림이 주어져 있어서 다행이였다. (4, 2)에..

문제https://www.acmicpc.net/problem/15684 15684번: 사다리 조작사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선www.acmicpc.net 접근법N이 10이하, H가 30이하이기 때문에 완전 탐색으로 풀어도 되겠다고 생각했다. 그리고 놓여진 가로선의 개수가 최솟값보다 큰 경우와 3보다 큰 경우를 가지치기 할 수 있기 때문에 백트래킹을 사용했다. 문제에서 보여주고 있는 사다리를 2차원 배열로 표현하였고, 아래와 같이 배열의 값을 통해 사다리 존재 여부를 판단했다. 0: 빈칸1: 왼쪽으로 이동할 수 있는 사다리 존재2: 오른쪽으로 이동..

문제https://www.acmicpc.net/problem/14890 14890번: 경사로첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.www.acmicpc.net 접근법각 행과 열 마다 경사로를 설치할 수 있는지 확인하면 된다. 경사로를 설치할 수 있는 조건을 간단히 정리하면 높이의 차가 1인 곳에서 낮은 곳에 L만큼 설치할 수 있는 칸이 존재하면 된다. 나는 (r, c)에서 direction(수평 or 수직) 방향으로 경사로를 설치할 수 있으면 true, 아니면 false를 반환하는 함수를 만들었다. -> 가독성이 안 좋고 어차피 (0, i)와 (i, 0)에서 검사를 시작하도록..

문제https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터www.acmicpc.net 접근법문제 그대로 구현하면 되는 쉬운 문제이다. 톱니바퀴를 나타내는 클래스를 하나 만들고, 시계 또는 반시계 방향으로 움직이는 메서드를 만들었다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class ..