전체 글312 [JAVA] 백준 2589 - 보물섬 https://www.acmicpc.net/problem/2589N X M 지도가 주어지면, 보물의 위치의 최단거리를 구하는 문제이다. 근데 보물의 위치가 최장거리라서 사실 MAX값 구하기 문제이다.N과 M의 크기가 50으로 작아서 완전탐색으로 BFS를 돌렸다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;public class Main { static int[] dx = {0,0,1,-1}; static int[] dy = {1,-1,0,0}; .. 2025. 10. 20. [JAVA] 백준 2151 - 거울 설치 https://www.acmicpc.net/problem/2151 집 안에 거울을 설치해서 한쪽 문에서 다른 쪽 문을 거울을 통해 바라볼 수 있게 되는 거울 설치 개수의 최솟값을 구하는 문제이다.처음에는 거울이 45도 기울어졌대서 대각선 이동인줄알고 그렇게 작성했는데 보니까 거울이 45도로 기울어져 있으면 빛의 진행방향이 90도 꺾이는 구조였다. 빈 공간을 만난 경우 진행했던 방향으로 계속 직진을 해야하고, 거울을 설치할 수 있는 공간을 만나면 설치하지 않고 빈 공간처럼 진행하거나, 입장 방향의 수직방향으로 꺾어서 진행할 수 있다.따라서 진행 방향을 저장해야했고, 진행 방향별 방문체크와 가중치를 저장하면서 진행했다.도착지점은 최대 4방향에서 접근 가능하므로 dist배열에 4방향의 최소 가중치를 저장한 뒤.. 2025. 10. 19. [JAVA] 백준 3671 - 산업 스파이의 편지 https://www.acmicpc.net/problem/3671주어진 최대 7개의 숫자로 만들수 있는 소수의 개수를 출력하는 문제이다.만들수 있는 숫자의 최댓값이 9,999,999이므로 1천만 이하의 수에서 에라토스테네스의 채로 소수를 거르고,DFS로 최댓값 이내로 모든 경우를 탐색 후 중복 없는 소수의 개수를 출력했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static boolean[] era = new boolean[10000000]; static int count = 0; static Hash.. 2025. 10. 19. [JAVA] 백준 1720 - 타일 코드 https://www.acmicpc.net/problem/17202XN 타일을 각각 1X2, 2X2, 2X1 타일로 채우는 방법의 가짓수를 구하되, 대칭인 경우는 1개로 취급하는 가짓수를 구하는 방법이다. 전체 가짓수를 구하고, 대칭인 가짓수를 제외해주면 되는데, 홀수인경우 대칭이려면 가운데 1X2타일을 끼고 대칭인 케이스밖에 없고, 짝수인 경우는 절반이 완전히 대칭인 케이스와 가운데에 2칸을 낀 상태로 나머지 칸들이 대칭인 경우가 있다.2칸을 채우는 방법은 2X2 혹은 2X1두개를 이용해 채울 수 있다. 1X2두칸은 절반이 완전히 대칭인 케이스에 포함이라 제외했다. import java.io.BufferedReader;import java.io.IOException;import java.io.Input.. 2025. 10. 18. [JAVA] 백준 16949 - 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946 1과 0으로 이루어진 2차원 배열이 주어지며, 1은 벽이고 0은 빈 공간일 때, 각 벽을 부쉈을 때 도달가능한 빈 공간의 개수(부순 벽 포함) -> 빈 공간 영역의 각 칸수의 합 + 1이다. 각 영역에 번호를 붙인 뒤 탐색한 칸수를 쌍으로 HashMap에 저장하고 벽을 탐색하며 인접한 영역의 칸수를 더한 뒤 1을 더하고, 10으로 나눴다. 마지막 과정을 stream + distinct + toArray로 했다가 시간초과, Set으로 바꿔도 시간초과가 나서 결국 초기 탐색 방식을 DFS를 BFS로 수정하고 통과했다. import java.io.BufferedReader;import java.io.IOException;import java.. 2025. 10. 18. [JAVA] 백준 1722 - 순열의 순서 https://www.acmicpc.net/problem/1722순열의 길이 N과 소문제 번호와 관련 데이터가 주어졌을 때 정답을 출력하는 문제이다.1번 소문제는 숫자 K가 추가로 주어지며 길이 N으로 만들 수 있는 사전 순 K 번째 순열을 출력하는 문제이고,2번 소문제는 순열이 주어졌을 때 이 순열이 몇번째 순열인지를 출력하는 문제이다.첫번째 문제는 먼저 한 숫자가 고정되었을 때 순열의 개수를 구하는데에서 시작했는데, 이는 (N-1)!이다.길이 N의 순열의 개수가 N! = N X N -1 X ... X 2 X 1일 때 N을 1로 치환한 값이기 때문이다.따라서 N이 4라면 개수는 4!=24이고 첫번째 자리에 들어올 수 있는 1~4의 숫자들이 3!=6 개씩 경우의 수를 차지한다.그러므로 K가 주어졌을 때 .. 2025. 10. 17. 이전 1 2 3 4 ··· 52 다음