기록방

👉 문제링크 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 🔸 문제 분석 🔸 9x9 스도쿠 문제가 주어지면, 빈칸을 채워서 출력하는 문제이다. 🔸 문제 풀이 🔸 스도쿠 규칙에 따라 가로, 세로, 정사각형에 겹치는 숫자가 없도록 숫자를 채워가야 한다. 만약 숫자를 놓지 못하는 경우가 생기면, 직전에 놨던 숫자를 취소하고 다시 놓아 보아야 하기 때문에 백트래킹이 필요하다. 백트래킹에서 가로, 세로, 정사각형에 겹치는 숫자가 있는지에 대한 상태 정보도 필요하다. 숫자를 채워가며 마지막 칸까지 채우는데 성공하면, ..

👉 문제링크 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 🔸 문제 분석 🔸 N x N 게임 판에서 2048을 수행한다. 5번 수행했을 때 최대값을 출력한다. 🔸 문제 풀이 🔸 2048게임 규칙에 따라 구현하면 되는 문제이다. 이동 방향에 따라 모든 칸의 숫자가 이동한다. 같은 숫자는 합쳐지고, 같은 회차에서 더이상 합쳐지지 않는다. 먼저 움직인 숫자가 먼저 합쳐진다. 최대값을 찾기위해 5회 게임 횟수의 모든 경우의 수를 확인한다. 풀이는 DFS로 탐색하였다. 🔸 코드 🔸 impo..

👉 문제링크 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🔸 문제 분석 🔸 N개의 자연수 중 M개를 고른 수열을 모두 구한다. 수열은 중복되선 안되며 사전 순으로 증가하는 순서로 출력한다. N개의 자연수는 중복이 있을 수 있다. 순열로 M개의 원소를 고르고, 중복을 제거하면 된다. 🔸 코드 🔸 import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.StringTokenizer; public cla..

👉 문제링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 🔸 문제 분석 🔸 N명 중에서 N/2명을 뽑았을때 나오는 시너지 차이의 최소값을 출력한다. N명에서 N/2를 뽑는 조합 문제이다. 반대 팀으로 뽑히면 같은 값을 중복으로 검사하게 되지만, 시간복잡도가 허용범위 내이므로 감안해도 된다. 조합으로 뽑아 시너지 차이의 최소값을 업데이트한다. 🔸 코드 🔸 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..

👉 문제링크 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 🔸 문제 분석 🔸 9 x 9 스도쿠의 빈칸을 채우는 문제이다. 스도쿠는 가로, 세로, 소속 3x3 칸에 중복되는 숫자가 없어야 한다. 여러 개의 답 중 사전식으로 앞서는 것을 출력한다. 그리디하게 접근해서 좌상단부터 우하단으로 넣을 수 있는 작은 수들을 넣다보면 넣을수 없는 경우가 생긴다. 따라서 넣을 수 없는 경우는 다시 돌아가서 다음 숫자를 넣어봐야 하므로 백트래킹을 사용한다. 🔸 코드 🔸 import java.io.BufferedReade..