본문 바로가기

분류 전체보기1502

[백준] 1987 알파벳 - Backtracking / Java • 문제 링크 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int r, c, ma.. 2022. 9. 23.
[백준] 16987 계란으로 계란치기 - Backtracking / Java • 문제 링크 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int n, ma.. 2022. 9. 22.
[백준] 17136 색종이 붙이기 - Backtracking / Java • 문제 링크 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net • 풀이 과정 10 * 10 크기의 2차원 배열에 색종이를 붙일 수 있는 면적에 대한 정보를 입력받고 크기가 1 * 1 ~ 5 * 5 인 각각의 색종이의 사용 가능한 개수를 기록할 paper 배열을 생성한다. 전체 면적을 재귀 함수를 활용하여 최상단 행에서 우측으로 모두 탐색 후, (x == 10) 아래 행으로 내려가는 방식(recur(y + 1, 0, cnt)) 으로 탐색한다. 만약 현재 좌표가 색종이를 붙일 수 없는 좌표라면 다음 x 축.. 2022. 9. 21.
[백준] 16945 매직 스퀘어로 변경하기 - Backtracking / Java • 문제 링크 16945번: 매직 스퀘어로 변경하기 1부터 N2까지의 수가 하나씩 채워져 있는 크기가 N×N인 배열이 있고, 이 배열의 모든 행, 열, 길이가 N인 대각선의 합이 모두 같을 때, 매직 스퀘어라고 한다. 크기가 3×3인 배열 A가 주어졌을 때, www.acmicpc.net • 풀이 과정 3 * 3 배열에 각 좌표의 정수 값을 입력받고, 각각의 정수를 사용했는지 확인할 boolean 형 배열을 생성한다. 백트래킹을 통해 최상단 행에서부터 가로로 값을 변환하는 모든 경우의 수를 구하며, 변환 비용을 sum 에 누적(sum + Math.abs(tmp - i)) 시킨다. 해당 행 완료(x == 3) 시 아래 행으로 넘어가는 방식(recur(y + 1, 0, sum)) 으로 사각형을 채울 수 있는 .. 2022. 9. 20.
[백준] 15684 사다리 조작 - Backtracking / Java • 문제 링크 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net • 풀이 과정 n개의 세로선에 h개의 점선이 가로로 교차되어 있는 사다리에 m개의 가로선의 정보를 입력받는다. 2차원 boolean 배열에 입력받은 좌표 기준 오른쪽 방향에 가로선이 있을 시 true 로 저장한다. 가로선은 없거나 최대 3개까지 사용 가능하므로 가로선이 0 ~ 3개 추가로 설치한 경우를 모두 확인한다. 재귀 함수(recur) 의 2중 for문에서 현재 위치 기준 오른쪽 방향으로 가로선이 존재하지 않을 경우 (!map[i][j]) 백.. 2022. 9. 19.
[백준] 14889 스타트와 링크 - Backtracking / Java • 문제 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int n; static int[][] stat; s.. 2022. 9. 18.

티스토리툴바