본문 바로가기

전체 글1321

[백준] 16938 캠프 준비 - Brute Force / Java • 문제 링크 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net • 풀이 과정 문제의 개수 n, 조건값 l, x, r 과 각 문제의 난이도를 입력받아 크기가 n인 배열 arr 에 저장 및 오름차순 정렬한다. 재귀 호출 함수에 문제 난이도 값의 합 sum, 선택된 난이도의 최솟값 min, 최댓값 max 와 함수 내부의 반복문의 시작값 idx, 재귀 함수의 깊이 depth 값을 매개 변수로 전달하여 실행한다. 배열에 저장된 값을 sum 변수에 더한 값, 해당 값을 최소값, 최대값과 비교해 갱신한 값, 중복된 문제를 선택하지 않기 위해 i + 1 과 문제 하나가 추가로 선택됐음을 나타내는 depth + 1 을 매개 변수로 전달해 .. 2022. 8. 5.
[백준] 16937 두 스티커 - Brute Force / Java • 문제 링크 16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net • 풀이 과정 예제 입력에 따르면 스티커의 형태는 직사각형이며, 스티커가 90도 회전 가능하므로 각각의 스티커 당 2가지 경우로 붙일 수 있음을 알 수 있다. 따라서 스티커 정보들을 입력받을 때 90도로 회전하거나 회전하지 않는 두 경우를 제네릭이 Node 클래스인 List 객체에 세로값과 가로값을 교차하여 저장하고, 각각의 스티커를 구분하는 id 값은 같게 저장한다. 이렇게 두 스티커를 조합하는 모든 경우의 수를 구하는데, List 객체에서 각각의 스티커 정보를 꺼내어 boolean 배열 visit 의.. 2022. 8. 4.
[백준] 16924 십자가 찾기 - Brute Force / Java • 문제 링크 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net • 풀이 과정 문제에 대한 접근 방식은 * 로 만들 수 있는 십자가를 찾는 것이 아닌, 갖가지 크기의 십자가만이 주어졌을 때 예제 입력의 상태로 만들 수 있는 지를 찾는 것이다. 따라서 십자가를 적용할 수 있는 시작점을 map 배열의 n - 1 * m - 1 의 범위내에서 찾고 해당 시작점에서 4 방향을 모두 탐색 가능할 시, 십자가를 적용할 수 있는 경우이므로 탐색한 모든 좌표를 boolean 배열에 방문 표시한다. 십자가의 개수를 나타내.. 2022. 8. 3.
[백준] 2580 스도쿠 - Backtracking / Java • 문제 링크 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net • 풀이 과정 입력받은 스도쿠 판의 값 중 비어있는 칸의 좌표를 제네릭이 Node 클래스인 List 객체 list 에 저장한다. 재귀 호출 함수 recur 에서 비어있는 좌표의 y, x 값을 list 에서 꺼내어 해당 값이 속한 가로, 세로축을 모두 탐색하고 3 * 3 정사각형을 탐색할 시작점의 좌표를 ny, nx 라 하였을 때 ny = y / 3 * 3, nx = x / 3 * 3 을 통하여 시작점을 구할 수 있다. 예시로 y, x 값이 2, 5.. 2022. 8. 2.
[백준] 16943 숫자 재배치 - Backtracking / Java • 문제 링크 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net • 풀이 과정 입력받은 문자열 a를 순열으로써 charAt() 으로 인덱스를 탐색하고, boolean 배열을 활용한 백트래킹으로 구한다. 이때 문제에 주어진 조건 상 구해진 순열이 0 으로 시작하면 안되고 b 보다 작거나 같아야 하므로 순열의 하나의 경우의 수를 c 이고 탐색을 수행할 반복문의 인덱스를 i 라고 할 때, 현재 문자열 a 에서 탐색한 숫자가 0 이거나 (a.charAt(i) - '0' == 0), 구해진 순열이 .. 2022. 8. 1.
[백준] 16922 로마 숫자 만들기 - Backtracking / Java • 문제 링크 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net • 풀이 과정 4개의 수 중에서 n개의 순열을 찾되, 서로 다른 수를 찾아야 하는 문제의 조건을 고려하여야 한다. 예를 들어 n = 6 일 때, I I I I I L = 1 + 1+ 1+ 1+ 1 + 50 = 55, V X X X X X = 5 + 10 + 10 + 10 + 10 + 10 = 55 과 같이 합이 중복인 값이 존재한다. 따라서 1 ≤ N ≤ 20 조건에 의해 합의 최대 값은 50 * 20 = 1000, 인덱스의 범위를 벗어나지 않기 위해 크기가 1001 인 boolean 배열을 생성하여 중복을 검사한다. 백트래킹을 활용하여 순열의 .. 2022. 7. 31.

티스토리툴바