문제 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 8 X 8 크기의 확인용 배열을 활용하여 입력받은 체스판 배열에서 최소값을 찾아내면 된다. 최소값을 찾는 방법은 for문을 통해 해당 배열의 각 칸을 확인하고, 해당 칸이 홀수 자리에 있는지 짝수 자리에 있는지 확인한다. 그리고 그 칸이 'B'인지 'W'인지를 판별하여 자리에 맞지 않는 색일 경우 값을 증가해주면 된다. 코드 import java.util.* import kotlin.math.* fun main() { val br = Syste..

문제 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 풀이 지그재그 순서의 분수를 차례대로 나열하고 열 별로 살펴보면 규칙성을 찾을 수 있다. 1열: 1/1 2열: 1/2 2/1 3열: 3/1 2/2 1/3 4열: 1/4 2/3 3/2 4/1 5열: 5/1 4/2 3/3 2/4 1/5 1열의 분모 + 분자 = 2, 2열의 분모 + 분자 = 3인 것처럼 각 열마다 분자와 분모를 더하면 열의 값 + 1이 된다. 이 규칙을 활용해 입력받은 숫자가 몇 번째 열에 속하는지 계산할 수 있다. 분모와 분자를 더한 값을 나타내는 sum 변수와 분수의 순번을 나타내는 tmp변수를 선언한다. while문을 통해 tmp가 입력받은 num보다 작을 때까지 tmp..

문제 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출..

문제 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 이 문제는 백트래킹을 활용하여 가능한 모든 조합을 찾는 문제이다. 백트래킹은 깊이 우선 탐색(DFS)를 기반으로하는 알고리즘으로, 일반적인 DFS와는 차이점이 있다. 일반적인 DFS는 가능한 모든 경로를 탐색하는데, 때로는 불필요한 경로까지 모두 탐색하며 경우의 수를 최적으로 줄이지 못할 수 있다. 반면 백트래킹은 해를 찾는 도중 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 다른 해를 찾아 탐색한다. 이렇게 하면 불필요한 계산을 피하고..

문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 풀이 문제는 시작점부터 도착점까지 도달 가능한 경로 수를 구하는 것이다. 처음엔 DFS로 시도했지만 시간초과가 발생하여 반복문과 DP를 활용한 풀이를 하였다. 시작점인 dp[0][0]에 1을 할당하고, 반복문을 통해 각 위치까지의 도달 가능한 경로 수를 구한다. dp[i][j]가 0인 배열은 처리하지 않고 넘어가도록 하며 0이 아닌 경우에는 오른쪽과 아래 방향으로 map[i][j]만큼 이동 한 후, 그 지점의 dp 배열에 현재 위치 경로 수를 더..