ImJay

[BOJ/Java] 1463. 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 해석 이 문제는 주어진 수 𝑋X를 1로 만드는 데 필요한 최소 연산 횟수를 찾는다. 연산은 다음 세 가지 중 하나를 선택할 수 있다: 𝑋X가 3으로 나누어 떨어지면, 3으로 나눈다. 𝑋X가 2로 나누어 떨어지면, 2로 나눈다. 𝑋X에서 1을 뺀다. 풀이 과정 이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있다. 각 숫자 𝑖i에 대하여, 𝑖i를 1로 만드는 최소 연산 횟수를 dp[i] 배열에 저장한다. 점화식은 다음과 같다: 𝑑𝑝[𝑖]=𝑑𝑝[𝑖−1]+1 𝑑𝑝[𝑖]=min⁡(𝑑𝑝[𝑖],𝑑𝑝..

[BOJ/Java] 1753. 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해석 이 문제는 주어진 그래프에서 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 고전적인 다익스트라 알고리즘 문제다. 주어진 그래프는 방향성이 있으며, 각 간선에는 가중치가 존재한다. 풀이 과정 제출된 코드는 다음 단계로 문제를 해결한다: 입력 받기: 각 간선 정보를 입력받아 인접 리스트에 저장한다. 다익스트라 알고리즘 실행: 우선순위 큐를 사용하여 현재 정점에서 가장 ..

[BOJ/Java] 11562. 백양로 브레이크 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 문제 해석 이 문제는 학교의 건물 간 통행로를 양방향으로 통행할 수 있게 만드는 데 필요한 최소 비용을 계산하는 문제이다. 각 통행로는 일방통행 또는 양방향 통행이 가능하며, 일방통행로를 양방향으로 바꾸는 데에는 비용이 든다. 풀이 과정 제출된 코드는 플로이드-와샬 알고리즘을 사용하여 모든 쌍 최단 경로를 계산한다. 각 건물 간의 최소 비용을 담은 그래프에서, 일방통행로의 경우 양방향으로 변경할 때 추가 비용을 고..

[BOJ/Java] 2457. 공주님의 정원 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 문제 해석 본 문제에서는 공주님의 정원을 3월 1일부터 11월 30일까지 꽃으로 가득 채우기 위해 필요한 최소한의 꽃 종류를 선택하는 방법을 찾는다. 각 꽃은 피는 시기와 지는 시기가 정해져 있으며, 이를 효과적으로 선택하여 연속적으로 꽃이 피어있게 해야 한다. 풀이 과정 제출된 코드는 꽃들의 생장 기간을 기반으로 그리디 알고리즘을 사용하여 문제를 해결한다. 모든 꽃들을 피는 시기를 기준으로 정렬하..

[BOJ/Java] 17070. 파이프 옮기기 1 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 해석 이 문제는 주어진 격자 안에서 파이프를 조작하여 시작 위치에서 목표 위치까지 이동하는 경로의 수를 찾는 문제다. 파이프는 가로, 세로, 대각선의 3가지 상태로 움직일 수 있으며, 격자의 범위와 벽(값 1)에 의해 움직임이 제한된다. 파이프는 격자의 한 쪽 끝에서 다른 쪽 끝으로만 연장될 수 있으며, 목적지에 도달할 때마다 가능한 경로의 수를 세어야 한다. 풀이 과정 제출된 코드는..

[BOJ/Java] 17281. ⚾ 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 문제 해석 이 문제는 야구 게임의 이닝과 플레이어의 타격 결과를 기반으로 최대 점수를 계산하는 문제이다. 각 선수가 타석에 서서 결과를 내는 순서인 타순을 조정하여 가장 많은 점수를 얻을 수 있는 경우를 찾아야 한다. 문제의 주요 요소는 다음과 같다 1번 선수는 항상 4번 타자로 고정. 나머지 선수들의 타순을 조합하여 최대 점수를 계산. 각 선수의 타격 결과에 따라 주자들이 진루하며, 홈을 통과하면 점수를 획득. 풀이 과정 제출된 코..

[BOJ/Java] 17472. 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제 해석 '다리 만들기 2' 문제는 지도에서 여러 섬들을 최소 비용의 다리로 연결하여 모든 섬이 연결되도록 하는 최소 스패닝 트리를 구하는 문제다. 각 칸은 바다 또는 섬으로 표시되며, 다리는 바다 위에만 세울 수 있고, 다리의 길이는 2 이상이어야 하며 직선으로만 연결 가능하다. 이 문제를 풀기 위해 그래프의 최소 스패닝 트리를 구하는 크루스칼 알고리즘을 사용한다. 풀이 과정 섬 구분: 입력..

[BOJ/Java] 1759. 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 해석 이 문제는 주어진 문자들 중에서 L개를 선택해 가능한 암호를 만드는 문제다. 암호는 최소 한 개의 모음과 두 개의 자음으로 구성되어야 하며, 알파벳 순서대로 배열되어야 한다. 풀이 과정 입력으로 주어진 문자들을 모음과 자음으로 분류한다. 가능한 모든 모음과 자음의 조합을 찾아서 암호를 생성한다. 이때, 모음은 최소 1개에서 최대 L-2개 사이, 자음은 최소 2개에서 최대 L-1개 사이여야 한다. 모음과 자음의 선택..

[BOJ/Java] 13023. ABCDE 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 해석 이 문제는 친구 관계를 나타내는 그래프가 주어졌을 때, A-B-C-D-E와 같이 서로 친구인 5명이 연속으로 이어지는 관계를 찾는 문제다. 이는 그래프에서 길이가 4인 경로를 찾는 것과 동일하다. 풀이 과정 각 사람의 친구 관계를 양방향 그래프로 표현하고, 인접 리스트로 구현한다. 각 노드를 시작점으로 하여 깊이 우선 탐색(DFS)을 실행한다. 각 노드에서 시작할 때, 해당 노드를 방문한 것으로 표시한다. DFS를 통해 깊이가 4가 되는 순간을 찾는다. 깊이가 4가 되면 5명이 연속으로 이어진 것이므로 답을 찾은 것..

[BOJ/Java] 15683. 감시 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 문제 해석 이 문제는 CCTV가 설치된 감시 시스템을 통해 주어진 사무실의 블라인드 스팟(사각지대)의 최소 영역을 구하는 시뮬레이션 문제다. 각 CCTV는 특정 방향으로만 감시할 수 있으며, 각 CCTV의 종류에 따라 감시할 수 있는 방향이 정해져 있다. 목표는 모든 CCTV의 방향을 조정하여 사각지대의 면적을 최소화하는 것이다. 풀이 과정 입력을 받아 사무실의 크기, 각 칸의 상태, 그리고 CCTV의 위치와 종류를..