자바/백준
-
[17136] 색종이 붙이기 - Java[자바]자바/백준 2023. 9. 30. 01:00
| 문제 링크 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net | 문제 1x1, 2x2, ..., 5x5 크기의 색종이가 5장씩 있습니다. 10x10 크기의 종이가 2차원 배열(0과 1)로 주어집니다. 색종이로 1만 모두 가릴 수 있는 최소한의 수를 출력하시오. 만약 주어진 색종이로 1을 모두 가릴 수 없는 경우 -1을 출력하시오. | 풀이 탐색을 시작하기 전에 행, 열 좌표, 칸수 i(1
-
[2623] 음악프로그램 - Java[자바]자바/백준 2023. 9. 29. 23:56
| 문제 링크 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net | 문제 N명의 가수와 M명의 보조 PD가 주어집니다. 보조 PD별로 계획한 가수들의 출연 순서를 고려해 가능한 출연 순서를 출력하시오. 출연 순서를 정할 수 없는 경우 0을 출력하시오. | 풀이 위상정렬 문제로 각 가수별 인접리스트(graph), 이전에 등장해야하는 가수의 수를 표현한 배열(degree) 를 구현합니다. 가수별로 사이클이 존재하는 경우 순서를 출..
-
[1948] 임계경로 - Java[자바]자바/백준 2023. 9. 29. 01:56
| 문제 링크 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net | 문제 사이클이 없으며, 일반통행 도로이고 모든 도시가 연결되어 있는 월드 나라의 지도를 만들 예정입니다. 한 도시에 도착할 수 있는 사람들이 모두 도착한 경우 다음 도시로 이동하는 규칙이 있으며 시작 도시부터 마지막 도시까지 걸리는 시간 1분도 안쉬고 정해진 경로를 다 달린 사람들의 도로 개수의 합 두 가지를 출력하시오. | 풀이 간단한 문제로 보았다가..
-
[1516] 게임 개발 - Java[자바]자바/백준 2023. 9. 28. 00:08
| 문제 링크 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net | 문제 세준 크래프트에서 건물은 건설하기 위해서 선행 건물이 필요한 건물과 선행 건물 없이 건설 할 수 있는 건물 두 가지가 있습니다. 모든 건물은 건설 가능하며, N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력하시오. (1 ≤ N ≤ 500) | 풀이 위상정렬로 풀이했으며, 우선 건물 별 다음으로 지을 수 있는 건물들을 인접리스트로 구현 & 각 건물 별 선행적으..
-
[2294] 동전 2 - Java[자바]자바/백준 2023. 9. 27. 18:38
| 문제 링크 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net | 문제 N개의 종류의 동전을 활용해 동전들의 합이 K가 되는 최소한의 동전 갯수를 출력하시오. 동전의 합으로 K를 만들 수 없다면 -1을 출력 | 풀이 길이가 K+1인 배열을 생성합니다. i번째 배열의 값에 대해 동전을 하나씩 값을 탐색합니다. 동전의 크기보다 인덱스가 큰 경우에는 동전의 크기 만큼 전의 인덱스 값(해당 인덱스에는 해당 값을 구성한 ..
-
[2293] 동전1 - Java[자바]자바/백준 2023. 9. 27. 17:45
| 문제 링크 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net | 문제 N개 종류의 동전으로 K 금액을 만들 수 있는 경우의 수를 구하시오. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) | 풀이 DP 방식으로 문제를 풀었으며, 동전 하나(token1)를 기준으로(동전의 순서는 중요하지 않습니다) 1부터 K까지 금액별로 나올 수 있는 경우의 수를 배열(0번째 인덱스는 1로 설정)로 생성합니다. 1번에서 만든 배열을 활용하여 다음 동전 하나..
-
[17070] 파이프 옮기기1 - Java[자바]자바/백준 2023. 9. 26. 16:38
| 문제 링크 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net | 문제 첫째 줄에 입력 값 N(3 ≤ N ≤ 16)이 주어집니다. 그 다음줄 부터 0과 1로 이루어진 NxN 크기의 배열이 주어집니다. 파이프는 가로, 세로, 대각선 세 가지 종류이며, 이어질 수 있는 파이프의 종류와 조건은 다음과 같습니다. 가로 - 가로, 대각선 | 조건: 배열의 오른쪽 칸이 0이어야함 세로 - 세로, 대각선 | 조건: 배열의 아래 칸이..
-
[10868] 최솟값 - Java[자바]자바/백준 2023. 9. 22. 21:53
| 문제 링크 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net | 문제 입력 받은 정수들 중, a번 째 정수부터 b번 째 정수 중 최솟값을 찾는 문제 입니다. 해당 문제는 입력 받은 정수들의 구간 최솟값을 트리의 노드로 구현하는 세그먼트 트리 문제입니다. | 풀이 N≤2^k를 만족하는 최소한의 k를 구한 다음, 세그먼트 트리의 사이즈 2^(k+1)를 구해줍니다. N*4를 입력해도 됩니다. 루트를 기준으로 입력..