기록방

👉 문제링크 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔸 문제 분석 🔸 정수 N을 1로 만드는 가장 적은 연산 수를 출력한다. 연산은 -1, /3, /2 세 가지가 있다. DP, DFS, BFS 모두 풀이 가능하다. 🔸 DP 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { // Input BufferedReader br = new BufferedReader..

👉 문제링크 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 🔸 문제 분석 🔸 n * m 도화지에서 연결된 1의 개수의 최대값을 출력한다. BFS혹은 DFS로 연결된 1을 탐색한다. 연결된 1 무리의 개수와 그 중 최대값을 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import..

👉 문제링크 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 🔸 문제 분석 🔸 R x C 크기의 2차원 배열의 0번 열부터 C-1번 열까지 파이프를 연결하고자 한다. '.' 에는 파이프를 놓을 수 있고, 'x'에는 놓을 수 없다. 첫 열과 끝 열은 '.' 로만 채워져있다. 파이프는 오른쪽 위, 오른쪽, 오른쪽 아래로만 연결할 수 있다. 놓을 수 있는 파이프의 최대값을 출력한다. 🔸 풀이 전략 🔸 R이 최대 1만, C가 최대 500이므로 효율적인 선택 방법이 필요하다.(그리디) 최대한 많은 파이프를 두기 위해서는 가능한 위쪽으..

👉 문제링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 🔸 문제 분석 🔸 h x w 크기의 지도가 주어진다. 1은 땅, 0은 바다이다. 땅은 주변 8방향으로 건너다닐 수 있다. 건너다닐 수 있으면 같은 섬이다. 섬의 개수를 출력한다. BFS로 풀이할 수 있다. 지도의 모든 칸을 순회하며 확인한다. 땅을 발견하면 인접한 땅 모두를 체크한다. 체크한 땅은 다시 발견하지 않는다. 체크 횟수를 출력한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOEx..

👉 문제링크 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 🔸 문제 분석 🔸 고정된 위치의 숫자와, 그 사이에 하나 씩 들어갈 수 있는 4종류의 연산자들의 개수가 주어진다. 계산으로 만들 수 있는 값의 최대값과 최소값을 출력한다. 연산자 자리를 바꾸면 값이 달라지기 때문에 순열로 풀이할 수 있다. 같은 종류의 연산자는 자리를 바꿔도 중복계산이기 때문에 dfs나 nextpermutation으로 중복을 제거할 수 있다. 🔸 순열 🔸 import java.io..