본문 바로가기

Problem Solving1307

[백준] 1697 숨바꼭질 - Graph Theory / Java • 문제 링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net • 풀이 과정 너비 우선 탐색을 수행할 함수를 정의, 현재 위치(n) 와 도착 위치(k) 를 매개변수로 받고 큐에 현재 위치를 저장한다. 그리고 방문 여부를 확인할 chk 배열을 문제에 제시된 조건에 의해 100,001의 크기로 생성, 현재 위치를 1로 표시한다. 현재 위치는 loc 변수에, 다음으로 이동할 위치를 move 변수에 설정하며 3가지 이동 방법 (n + 1, n - 1, n * 2) 으로 이동한 모든 경우를 .. 2022. 6. 11.
[백준] 16953 A → B - Graph Theory / Java • 문제 링크 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) thr.. 2022. 6. 10.
[백준] 1541 잃어버린 괄호 - Greedy / Java • 문제 링크 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net • 풀이 과정 덧셈과 뺄셈이 혼재되어 있는 식에서 문제에 제시되어 있는 조건 상 최소 값을 구해내기 위해선 덧셈으로 이루어진 식을 괄호를 쳐서 먼저 계산한 후 뺄셈을 계산해야한다. 우선 전체식을 "-" 를 기준으로 분리하고 각각의 분리된 식에 포함된 수를 모두 더하는데 분리된 식을 문자열 파싱할 때 "+" 는 메타문자이므로 "\\+" 을 기준으로 파싱하며, 이때 생성된 모든 수를 더한 값을 result 변수에 뺄셈한다. 이때 result 변수.. 2022. 6. 9.
[백준] 13305 주유소 - Greedy / Java • 문제 링크 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net • 풀이 과정 우선 맨 처음 주유소는 다음 주유소로 이동하기 위해 필연적으로 이용해야 하며 마지막 주유소는 도착 지점이므로 계산에 포함되지 않는다. 각 주유소에 도달했을 때 해당 주유소의 가격이 다음 주유소의 가격보다 저렴하다면 다음 주유소에서 주유할 분량을 미리 주유하여 비용을 최소화하며 이는 현재 상황에서 최선의 수를 선택하는 그리디 알고리즘의 기본 원리에 부합한다. 첫번째 입력에서 이와 같은 규칙을 적용 시 5 2 4 1 -> 5.. 2022. 6. 8.
[백준] 1063 킹 - Implementation / Java • 문제 링크 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(Strin.. 2022. 6. 7.
[백준] 2980 도로와 신호등 - Implementation / Java • 문제 링크 2980번: 도로와 신호등 상근이는 트럭을 가지고 긴 일직선 도로를 운전하고 있다. 도로에는 신호등이 설치되어 있다. 상근이는 각 신호등에 대해서 빨간 불이 지속되는 시간과 초록 불이 지속되는 시간을 미리 구해왔 www.acmicpc.net • 풀이 과정 현재 위치(loc) 와 소요 시간(time) 을 나타내는 변수를 0으로 초기화, 이 후 각 신호등의 정보를 n회만큼 입력받는다. 1m 이동에 걸리는 소요 시간이 1초이므로 소요시간에 신호등 위치 - 현재 위치를 더해 시간의 경과를 나타내고, 현재 위치를 신호등의 위치로 갱신한다. r + g를 신호등의 한 주기로 정의 시 time % (r + g) 은 현재 시간이 신호등의 주기 중 몇 초를 진행 중인지를 나타내며, 이 시간(state) 이 .. 2022. 6. 6.

티스토리툴바