ImJay

[BOJ/Java] 17471. 게리맨더링 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 해석 이 문제는 N개의 구역을 두 그룹으로 나누어 각 그룹의 인구 차이를 최소화하는 문제이다. 각 구역의 인구수가 주어지고, 구역 간 연결 정보도 주어진다. 두 그룹은 각각 연결되어 있어야 하며(하나의 연결 요소를 이루어야 함), 불가능할 경우 -1을 출력한다. 풀이 과정 변수 선언 및 입력 처리: N은 구역의 수, num은 각 구역의 인구수를 저장하는 배열이다. 그래프 구성: 각 구역 간 연결 정보를 인접 리스트로 표현한 graph를 ..

[BOJ/Java] 17219. 비밀번호 찾기 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제 해석 이 문제는 주어진 웹사이트 주소에 대응하는 비밀번호를 빠르게 찾는 문제이다. 웹사이트 주소와 비밀번호 쌍이 N개 주어지고, M개의 웹사이트 주소에 대해 해당 비밀번호를 찾아 출력하는 구조이다. 풀이 과정 입력 처리: 사용자로부터 N (웹사이트-비밀번호 쌍의 수)과 M (조회할 웹사이트의 수)을 입력받는다. 해시맵 구성: N개의 웹사이트와 비밀번호 쌍을 읽어 해시맵에 저장한다. ..

[BOJ/Java] 17136. 색종이 붙이기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 해석 본 문제는 10x10 크기의 그리드에서 1로 표시된 부분을 최소 개수의 색종이로 모두 덮는 최적의 방법을 찾는 것이다. 사용 가능한 색종이의 크기는 1x1부터 5x5까지 다양하며, 각 크기의 색종이는 최대 5개까지 사용할 수 있다. 문제의 핵심은 최소한의 색종이 사용으로 모든 1을 덮는 것이다. 풀이 과정 초기화 및 입력 처리: 그리드를 10x10 크기의 배열로 초기화하고, 입력을 받아 해당 배열을..

[BOJ/Java] 16637. 괄호 추가하기 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 문제 해석 이 문제에서는 N개의 문자(숫자와 연산자)로 구성된 수식이 주어지며, 괄호를 적절히 추가하여 수식의 결과를 최대로 만드는 값을 찾아야 한다. 괄호는 중첩할 수 없으며, 한 번에 하나의 연산만을 포함할 수 있다. 풀이 과정 변수 선언 및 입력 처리: N은 수식의 길이, arr은 주어진 문자열을 담는 배열이다. 재귀 함수 설계: recursive 함수를 통해 괄호를 추가할 수 있는 모든 위치를 ..

[BOJ/Java] 3190. 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해석 이 게임에서 뱀은 격자 상에서 사과를 먹으며 이동하고, 자신의 몸이나 벽에 부딪히면 게임이 종료된다. 뱀은 처음에 오른쪽을 향하며, 일정 시간마다 방향 전환 명령을 받는다. 이 문제는 뱀이 사과를 먹거나 몸을 길게 하면서 주어진 명령에 따라 어떻게 움직이는지를 시뮬레이션해야 한다. 풀이 과정 이 Java 코드는 뱀의 움직임을 시뮬레이션하여 게임이 언제 종료되는지를 결정한다. 뱀의 머리 위치를 따라 움직이면서, 몸통을 나타내는..

[BOJ/Java] 14500. 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해석 이 문제에서는 격자 위에 다양한 형태의 테트로미노를 놓았을 때 얻을 수 있는 점수의 최댓값을 찾는 문제다. 테트로미노는 모두 4개의 칸으로 구성되어 있고, 격자의 값에 따라 점수가 정해진다. 테트로미노는 90도 회전이나 대칭이 가능하다. 풀이 과정 Java 코드는 DFS(깊이 우선 탐색)를 사용하여 격자에서 가능한 모든 테트로미노의 위치를 탐색하고, 그 중 최댓값을 찾는다. 각 테트로미노는 최대 4개의 칸으로 ..

[BOJ/Java] 3055. 탈출 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해석 이 문제는 고슴도치가 물이 차오르는 동굴에서 탈출구로 이동하는 최소 시간을 찾는 시뮬레이션 문제이다. 동굴은 격자로 표현되며, 고슴도치는 매 초마다 인접한 네 방향으로 이동할 수 있다. 물도 매 초마다 인접한 네 방향으로 확장된다. 고슴도치는 물이 있는 칸이나 돌이 있는 칸으로 이동할 수 없으며, 탈출구에 도달하면 게임이 종료된다. 탈출이 불가능한 경우도 고려해야 한다. 풀이 과정 Java 코드는 BFS(너비 우선 탐색)를 사용..

[BOJ/Java] 2174. 로봇 시뮬레이션 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 문제 해석 이 문제는 격자 위에서 주어진 명령에 따라 로봇들을 움직이면서, 로봇이 벽에 부딪히거나 다른 로봇과 충돌하는 상황을 시뮬레이션하는 문제이다. 로봇은 네 방향 중 하나를 향하고 있으며, "F", "L", "R" 세 가지 명령을 수행할 수 있다. "F"는 전진, "L"은 좌회전, "R"은 우회전을 의미한다. 명령에 따라 로봇이 이동할 때마다 그 결과를 검사하여 충돌이나 벽에 부딪히는 상..

[BOJ/Java] 11403. 경로 찾기 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해석 이 문제는 주어진 방향 그래프에서 각 정점 𝑖에서 𝑗로 가는 경로가 존재하는지를 파악하는 문제다. 입력으로 주어지는 𝑁×𝑁 행렬에서, 행렬의 각 요소가 1인 경우 해당 정점 간에 직접적인 연결이 있음을 나타내며, 0은 연결이 없음을 나타낸다. 풀이 과정 플로이드-와샬 알고리즘을 사용하여 모든 정점 쌍 간의 가능한 경로를 찾는다. 이 알고리즘은 각 정점을 중간 정점으로 고려하며, 간접적인 경로도 고려하여 연결성을 파악한다. 코드 packag..

[BOJ/Java] 15652. N과 M (4) 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 해석 이 문제에서는 1부터 𝑁까지의 수 중에서 중복을 허용하여 𝑀개를 고르는 조합을 모두 찾는다. 선택된 수열은 비내림차순이어야 한다는 조건이 있어, 각 수열의 원소는 이전 원소보다 작아지지 않는다. 풀이 과정 문제의 요구 사항을 충족시키기 위해 재귀 함수를 사용하여 문제를 해결한다. 주어진 문제는 백트래킹 기법을 이용해 풀 수 있다. 재귀적으로 각 위치에 들어갈 수를 결정하고, 이전 선택된 수 이상의 숫자만..