본문 바로가기

Problem Solving/Baekjoon1324

[백준] 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.
[백준] 1759 암호 만들기 - Backtracking / Java • 문제 링크 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. 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.Arrays; import java.util.StringTokenizer; public class Main { s.. 2022. 9. 17.
[백준] 16958 텔레포트 - Brute Force / Java • 문제 링크 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net • 풀이 과정 2차원 배열에 도시의 속성과 좌표를 입력받아 저장한다. 각 도시 간 이동시간을 구한 후, (Math.abs(map[i][1] - map[j][1]) + Math.abs(map[i][2] - map[j][2])) 두 도시가 특별한 도시일 경우 (map[i][0] + map[j][0] == 2) 해당 이동 시간과 텔레포트에 걸리는 시간 t 와 비교해 작은 값으로 저장한다. 이 후 플로이드 워셜 .. 2022. 9. 16.
[백준] 4902 삼각형의 값 - Brute Force / Java • 문제 링크 4902번: 삼각형의 값 입력은 여러 개의 테스트 케이스로 이루어져 있고, 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 줄의 수를 나타내고, 다음 숫자는 단위 삼각형에 적혀있는 값이 위에서 아래, 왼 www.acmicpc.net • 풀이 과정 삼각형을 2차원 배열로 구현하여 단위 삼각형의 값을 입력받고, 각 행(삼각형의 층) 의 누적합을 pSum에 저장한다. 이 후 부분 삼각형이 정삼각형인 경우와 역삼각형인 경우의 수를 두 개의 2중 for 문을 통하여 구한다. 삼각형의 각 열(각 층의 단위 삼각형의 개수) 은 (2 * 행) - 1 의 길이를 가지므로, 모든 부분 정삼각형은 반복문의 범위(i = 1 ~ n, j = 1 ~ (2 * i) - 1) 에서 (i , j) 를 상단 .. 2022. 9. 15.
[백준] 17471 게리맨더링 - Brute Force / Java • 문제 링크 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net • 풀이 과정 각 구역의 번호를 인덱스로 지정하는 value 배열에 인구 값을 입력받고, 인접행렬에 각 구역과 인접한 구역의 정보를 입력받아 인접할 시 1로 저장한다. 구역을 둘로 나누기 위해 한 구역은 subset 배열의 true, 다른 한 구역은 false 로 나타내며, 재귀 함수(recur) 를 통해 구역을 둘로 나누는 모든 경우의 수를 각 구역의 값의 합을 누적하며 구한다. 경우의 수가 구해지면, 매개변수를 true 또는 false 로 전달받는 isConnecte.. 2022. 9. 14.

티스토리툴바