본문 바로가기

백준114

[백준] 1931번 회의실 배정 JAVA (자바) 풀이 문제 1931(그리디, 정렬) :  한 개의 회의실, N개의 회의, 회의실 사용표 :  각 회의 I에 대해 시작시간과 끝나는 시간    각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기  :  회의는 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의 시작    (회의의 시작시간과 끝나는 시간이 같다면 시작하자마자 끝나는 회의)  [입력] :  첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000) :  둘째 줄부터 N+1 줄까지 각 회의의 시작시간과 끝나는 시간    (시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0)    [출력] :  첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력    [문제접근]  1. 정렬 이용하.. 2024. 7. 17.
[백준] 2636번 치즈 JAVA (자바) 풀이 문제 2636(BFS)  : 회색으로 표시된 부분 = 치즈   X친 부분 = 판의 가장자리 (치즈 없음)   ‘c’로 표시된 부분만 한 시간 후에 녹고 빈칸과 접촉하는 치즈는 c 표시 해준다   단 치즈로 둘러쌓여있는 빈칸은 접촉해도 c표시 없어도 된다 :  치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각 개수 구해라  [입력] :  첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수 (길이는 최대 100)    판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지    (치즈가 없는 칸은 0, 치즈가 있는 칸은 1)     [출력] :  첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력 :  둘째 줄에는 모두 녹기 한 시간.. 2024. 7. 13.
[백준] 3055번 탈출 JAVA (자바) 풀이 문제 3055(BFS)  :  티떱숲의 지도는 R행 C열로 이루어져 있다    비어있는 곳은 .    물이 차있는 지역은 *    돌은 X    비버의 굴은 D    고슴도치의 위치 S  :  매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동가능    물도 매 분마다 인접한 비어있는 칸으로 확장    물과 고슴도치는 돌을 통과할 수 없다    고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다  :  고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램    (다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다)  [입력] :  첫째 줄에 50보다 작거나 같은 자연수 R과 C :  다음 R개 줄에는 티떱숲의 지도 .. 2024. 7. 12.
[백준] 9019번 DSLR JAVA (자바) 풀이 문제 9019(BFS)  :  네 개의 명령어 D, S, L, R    계산기에는 레지스터 = 0 이상 10,000 미만의 십진수 저장 가능     예) 레지스터에 저장된 n (n의 네 자릿수를 d1, d2, d3, d4)          즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D = n x 2 (결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지)S = n - 1 (n이 0 이라면 9999 가 대신 레지스터에 저장)L = n의 각 자릿수를 왼편으로 회전 (d2, d3, d4, d1)R = n의 각 자릿수를 오른편으로 회전 (d4, d1, d2, d3) :  A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램  [입력] :  첫 줄에 T 개의.. 2024. 7. 11.
[백준] 16234번 인구 이동 JAVA (자바) 풀이 문제 16234(BFS)  :  N×N크기의 땅    각 땅에는 나라가 하나씩 존재 ( r행 c열에 있는 나라에는 A[r][c]명이 산다)  :  인구 이동이 없을 때까지 지속된다.붙어있는 두 나라의 인구 차이가 L명 이상, R명 이하라면 인구 이동 시작인접한 칸만을 이용해 이동할 수 있으면 연합연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)편의상 소수점은 버린다연합을 해체하고 모든 국경선을 닫기 :  각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램  [입력] :  첫째 줄에 N, L, R (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)    둘째 줄부터 N개의 줄에 각 나라의 인구수    r행 c열에 주어지는 정수는 .. 2024. 7. 11.
[백준] 9205번 맥주 마시면서 걸어가기 JAVA (자바) 풀이 문제 9205(BFS)  :  출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발    맥주 한 박스에는 맥주가 20개     맥주 1병에 50미터 전진 가능    편의점에 들렸을 때, 빈 병은 버리고 새 맥주를 살 때 박스에 들어가는 총 맥주가 20병을 넘을 수 없다    (편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다)    편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다  [입력] :  첫째 줄에 테스트 케이스의 개수 t (t ≤ 50)    테스트 케이스의 첫째 줄에는 편의점의 개수 n (0 ≤ n ≤ 100)    다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 미터 좌표 ( -32768 ≤ x, y ≤ 32767)    두 좌표 사.. 2024. 7. 6.
[백준] 16928번 뱀과 사다리 게임 JAVA (자바) 풀이 문제 16928(BFS)  :  주사위를 조작해 원하는 수를 만들면 최소 몇 번만에 도착할까    게임은 크기가 10×10이고, 총 100개의 칸으로 된 보드판은 1~100까지 수가 적혀있다    주사위를 굴려 나온 수만큼 이동  :  예) 현위치 =  i  /  주사위 = 4라면 i+4번 칸으로 이동  :  도착칸 = 사다리 경우 위로 이동  /  도착칸 = 뱀 경우 뱀을 따라 이동    모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있다 (동시에 둘 다 갖는 경우는 없다)   :  게임의 목표 = 1번 칸에서 시작해서 100번 칸에 도착하는 것    100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 구하기  [입력] :  첫째 줄에 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(.. 2024. 7. 3.
[백준] 13549번 숨바꼭질 3 JAVA (자바) 풀이 문제 13549(BFS)  :  수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다     현 위치가 X일 때    걷기 = 1초 후에 X-1 또는 X+1로 이동    순간이동 =  0초 후에 2*X의 위치로 이동    수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해라  [입력] :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K  [출력] :  동생을 찾는 가장 빠른 시간을 출력    [문제접근] 1. 기존 숨바꼭질 1697번과 차이점!기존 문제에서는 모든 이동이 동일한 1초를 소요현 문제에서는 순간 이동은 0초 / 걷기 이동만 1초 소요 2. 출력 배열 사용하지 말고 큐에다 넣어버리기count[] 배열보다 .. 2024. 7. 3.
[백준] 11048번 이동하기 JAVA (자바) 풀이 문제 11048번 (DP) :  N×M 크기의 미로    1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다    현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다    (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동 가능, 각 방의 사탕 획득 가능    (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값  [입력] :  첫째 줄에 미로의 크기 N, M (1 ≤ N, M ≤ 1,000)    둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며 각각의 사탕의 개수 ( 0 ≤ 사탕 ≤ 100 )  [출력]  :  가져올 수 있는 사탕 개수를 출력  [설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지.. 2024. 7. 2.
[백준] 9184번 신나는 함수 실행 JAVA (자바) 풀이 문제 9184번 (DP) :  재귀함수 w(a, b, c)가 있다if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a   a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램   otherwise w(2a-2, 2b, c) 출력력  [입력] :  입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다    (입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다)  [출력]  :   w(a, b, c)를 출력  [설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  .. 2024. 7. 2.

티스토리툴바