문제 문제접근 방법 해당 문제는 정수 A를 네 가지 연산 D, S, L, R을 이용해 정수 B로 바꾸는 최단 연산 시퀀스를 구하는 과제이다. 입력은 테스트 케이스 수 T와 각 케이스의 두 정수 A, B(0~9999)이다. 출력은 A에서 B로 도달하는 최소 연산들의 문자열이다. 상태 공간은 0000부터 9999까지 10,000개 정수로 한정되며, 각 연산의 비용이 동일하므로 한 케이스당 최대 10,000개 상태와 각 상태당 4개의 전이를 고려하면 충분하다. 결국 핵심은 최단 경로를 보장하는 탐색을 수행하고, 그 결과를 연산 문자열로 복원하는 일이다.접근 방식은 BFS로 상태를 확장하며 목표를 만나면 즉시 중단하고, 탐색 중 기록한 이전 상태와 사용 연산을 이용해 역추적으로 연산 문자열을 복원하는 식으..
문제 문제접근 방법 해당 문제는 1~N까지 연속적으로 번호가 붙어있는 스위치가 존재하고 스위치가 ON일 때는 1, OFF일 때는 0으로 표시한다.이때 학생 몇 명을 뽑은 후 학생들에게 1~N 사이의 번호를 하나씩 나누어주며 학생의 성별에 따라 아래와 같이 스위치를 조작한다.남학생의 경우 스위치 번호가 자기 받은 번호의 배수이면 스위치 상태 변환시켜 주고여 자기 받은 번호와 같은 스위치 중심 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아 해당 구간 스위치 상태 모두 바꿔주는 것이다. 모든 조작이 끝나고 스위치들의 마지막 상태를 출력하는 프로그램을 작성하는 문제이다. 문제 접근 방법은 먼저 아래와 같이 문제를 이해하면서 요약하고 중요 부분들을 체크했다.위와 같이 문제를 요약하고 체크해야 하..
문제 문제접근 방법 해당 문제는 R x C 크기의 공간에 미세먼지와 공기청정기가 존재하고 1초마다 아래의 일들이 일어난다고 할 때T초 후에는 공간에 미세먼지가 얼마나 존재하는지를 구하는 문제이다.미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.확산되는 양은 Ar, c/5이고 소수점은 버린다. 즉, ⌊Ar, c/5⌋이다.(r, c)에 남은 미세먼지의 양은 Ar, c- ⌊Ar, c/5⌋×(확산된 방향의 개수)이다.공기청정기가 작동한다.공기청정기에서는 바람이 나온다.위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바..
문제 문제접근 방법 해당 문제는 N x M 크기의 공간에 아기 상어가 여러 마리 존재한다고 할 때 어떤 칸의 안전거리를 그 칸과 가장 거리가 가까운 아기 상어와의 거리라고 한다. 이동은 좌우상하 대각선 모두 가능하다고 한다면 안전거리의 최댓값이 몇인지를 출력하는 프로그램을 작성하는 문제이다.먼저 문제를 읽자마자 bfs를 활용하여 어떤 칸에서 상어에 도달할 수 있는 칸의 최소값을 구하고 그 최솟값들 중에서 최댓값을 구하면 되는 문제라고 이해해 아래와 같이 코드를 작성하였다. import java.util.*;public class Main{ public static int ocean[][]; public static int safeDistance=0; public static boo..
문제 문제접근 방법 해당 문제는 N x N크기의 체스판이 존재하고 N개의 퀸이 충돌하지 않는 경우의 수를 구하는 프로그램을 작성하는 문제로N은 입력값으로 주어진다. 처음 문제를 읽고 DFS를 통해 문제 해결이 가능할 것 같다는 생각은 했지만 대각선처리에 대한 생각이 많아져 어려움이 있었다.그래서 대각선을 고려하지 않고 초반에는 행과 열만 어떤 식으로 제한할지를 먼저 고민했다.그럼 체스에서 퀸이 어떤식으로 움직이는지를 알아야 하는데 퀸은 본인 위치 기준 상하좌우 우상 좌상 좌하 우하 대각선의 칸의 끝까지 움직일 수가 있다. 이미지로 보면 아래와 같이 움직일 수가 있는 것이다.이처럼 상하좌우 대각선 모든 범위를 제외하고 충돌하지 않는 N개의 퀸의 경우의 수를 구하는 것이다.그렇다면 어떤 경우가 가능..
문제 문제접근 방법 해당 문제는 캠핑을 갔는데 캠핑장에 연속하는 P일 중 L일만 사용가능하다는 경고문이 존재했다.이때 휴가를 V일이라 하면 휴가기간에 최대로 캠핑장을 이용할 수 있는 일 수를 구하는 프로그램을 작성하는 문제이다.문제를 읽어보니 총 휴가일을 P일로 나누고 문제를 접근하면 되겠다고 생각했고 아래와 같이 코드를 작성하였다. import java.util.*;public class Main{ public static void main(String args[]){ Scanner s=new Scanner(System.in); int i=1; while(true){ int l=s.nextInt(); int p=s..
