문제 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 배열에 현재 위치 경로 수를 더..

문제 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 토마토가 익는 과정은 동시에 일어나기 때문에 Queue를 이용한 BFS(너비 우선 탐색)으로 해결할 수 있다. 배열을 입력 받아 익은 토마토(1)인 경우에는 Queue에 추가해준다. 익지 않은 토마토(0)인 경우에는 익지 않은 토마토의 개수를 확인하는 변수인 cnt를 증가시켜준다. 이제 BFS를 실행하면 된다. 큐에서 하나의 위치를 꺼내어 상하좌우를 탐색하며 익지 않은 토마토(0)를 만나게 되면 cnt를 1 감소시키고 배열에 현재 날짜..