🔍 문제 읽기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 입력 출력 정수 N 정수 N의 연산을 사용하는 횟수의 최솟값 💡풀이 ❗️[핵심] DP 다이나믹 프로그래밍 초기값 d[1] = 0 점화식 ① 3으로 나누어 떨어짐 ➡︎ d[k] = d[k/3]+1 ② 2로 나누어 떨어짐 ➡︎ d[k] = d[k/2]+1 ③ 1을 빼면 ➡︎ d[k] = d[k-1]+1 ①, ②, ③ 중 최솟값 🧩코드
🔍 문제 읽기 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 입력 출력 자연수 N, M 1부터 N까지 자연수 중에서 M개를 고른 수 (중복 허용, 사전 순으로 증가하는 순서로 출력!) 4 2 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 💡 풀이 ❗️[핵심] 백트래킹 N과 M (1)에서 중복이 허용된다고 조건이 변형되어 출제된 문제다. N과 M (1)과 이 문제의 코드를 비교하여 어떤 부분이 중복을 걸렀는지 정확히 확인할 수 있다. 더보기 ..
🔍 문제 읽기 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 입력 출력 자연수 N, M 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 (단, 오름차순!) 4 2 1 2 1 3 1 4 2 3 2 4 3 4 💡 풀이 ❗️[핵심] 백트래킹 👉 오름차순으로 출력하므로 시작지점을 바로 이전에 저장한 값보다 1만큼 큰 값으로 설정한다. 🧩 코드
🔍 문제 읽기 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 입력 출력 자연수 N, M 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 (단, 수열은 사전 순인 증가하는 순서로 출력) 3 2 1 2 1 3 2 1 2 3 3 1 3 2 💡 풀이 ❗️[핵심] 백트래킹 arr 배열이 0-indexed인 점과 isUsed 배열은 1-indexed로 사용 혼동하지 않게 주의! 🧩 코드 더 많은 문제를 풀어 체화시키고 이해하도록 노력하자.
🔍문제 읽기 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 입력 출력 상자의 가로 크기 M, 세로 크기 N, 쌓아올리는 상자 수 H H개의 N*M 크기의 상자에 담긴 토마토 정보 (1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토 없음) 토마토가 모두 익을 때까지 최소 몇일 저장될 때부터 모든 토마토가 익어있으면 0 출력 토마토가 모두 익지 못하는 상황이면 -1 출력 💡풀이 사용언어 : cpp ❗️[핵심] 다차원 배열에서의 BFS (너비 우선) [백준] 7576번: 토마토 🔍..
🔍문제 읽기 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 입력 출력 N N*N 배열의 RGB 정보 ① 적록색약이 아닌 사람이 봤을 때 구역의 수, ② 적록색약인 사람이 봤을 때 구역의 수 🧑💻 사용언어 : cpp 💡풀이 ❗️[핵심] 다차원 배열에서의 BFS (너비 우선) ①적록색약인 사람 배열과 ②적록색약이 아닌 사람 배열을 선언하고 처음 색을 입력 받을 때, ①적록색약인 사람 배열에 G를 R로 저장한다. ⭐️ 인접한 칸을 방문할 때, ❗️적록색약인 사람과 아닌 사람 구분 👤적록색약인 사람 : R-..
🔍 문제 읽기 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ➡️ 요약 배추가 심어진 구역 당 배추흰지렁이 한 마리 필요 서로 상하좌우 인접하게 심어진 경우를 한 구역으로 취급 입력 출력 테스트케이스 개수 T 가로 길이 M, 세로 길이 N, 배추가 심어진 위치의 개수 K K개의 배추의 위치 (X, Y) 정보 필요한 배추흰지렁이의 마리 수 💡풀이 🧑💻 사용 언어: cpp ❗️[핵심] 다차원 배열에서의 BFS (너비 우선) [백준] 1926번: 그림 🔍 문제 읽기 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때..
🔍 문제 읽기 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 입력 출력 수빈이가 있는 위치 N, 동생이 있는 위치 K 수빈이가 동생을 찾는 가장 빠른 시간 💡풀이 👩💻 사용 언어 : Cpp ❗️[핵심] 다차원 배열에서의 BFS (너비 우선) 👉 BFS는 너비 우선이기에 최단시간을 구할 수 있다. 🧩 코드 1차원 배열이며, 조건도 까다롭지 않아 다소 쉽다.
🔍 문제 읽기 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 입력 출력 가로 크기 M, 세로 크기 N N*M 크기의 상자에 담긴 토마토 정보 (1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토 없음) 토마토가 모두 익을 때까지의 최소 날짜 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력 토마토가 모두 익지는 못하는 상황이면 -1을 출력 💡풀이 👩💻 사용언어 : cpp ❗️[핵심] 다차원 배열에서의 BFS (너비 우선) 👉 BFS는 너비 우선이기에 최단시간을 구할 수 있다...
🔍 문제 읽기 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 입력 출력 R(행)과 C(열) R x C 미로의 정보 (#: 벽, J: 지훈, F: 불, .: 이동 가능 공간) 미로를 탈출할 수 있는 경우 ➡︎ 가장 빠른 탈출시간을 출력 미로를 탈출 할 수 없는 경우 ➡︎ IMPOSSIBLE 을 출력 4 4 #### #JF# #..# #..# 3 💡풀이 👩💻 사용언어 : cpp ❗️[핵심] 다차원 배열에서의 BFS (너비 우선) 👉 BFS는 너비 우선이기에 최단시간을 구할 수 있다. ❗️ 문제..
