본문 바로가기

Problem Solving/Baekjoon1321

[백준] 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.
[백준] 1744 수 묶기 - Greedy / Java • 문제 링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net • 풀이 과정 수열의 합의 최대 값을 만들기 위해선 양수와 음수가 곱해져서 더 큰 음수를 만들지 않고, 음수와 음수끼리 곱하여 양수로 만들거나 0 와 음수를 곱하여 음수를 제거하여야 한다. 양수의 경우 내림차순으로 정렬하여 큰 순서대로 두 수를 곱하거나, 연산을 하는 두 수 중 1이 존재 할 시 두 수를 곱하는 대신 더한다. 따라서 양수는 양수끼리 연산하고, 음수는 0을 포함한 음수끼리 연산하여야 하므로 서로 다른 List 객체 pn (posit.. 2022. 7. 30.

티스토리툴바