본문 바로가기

boj127

[Java] BOJ 2623번 음악프로그램 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 위상정렬을 사용하여 해결했습니다. 코드 import java.io.*; import java.util.*; public class Main { public static int N, M; public static int[] in; public static int[][] adj; public static void main(String[] args) throws IOException { BufferedReader br = new Buffere.. 2021. 4. 23.
[Java] BOJ 11057번 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 0 1 2 3 4 5 6 7 8 9 합 1 자리 1 1 1 1 1 1 1 1 1 1 10 2 자리 10 9 8 7 6 5 4 3 2 1 55 3 자리 55 45 36 28 21 15 10 6 3 1 220 DP를 사용하여 위의 표처럼 계산을 진행하여 해결했습니다. 2자리일 때의 2로 시작하는 오르막 수는 2보다 크거나 같은 수들로 이뤄질 수 있으므로 2자리 바로 이전의 미리 구해둔 1자리일 때의 2 이상의 오르막 수 개수를.. 2021. 4. 22.
[Java] BOJ 9465번 스티커 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 처음 스티커를 선택하는 경우는 각각의 스티커를 가져오게 했습니다. 그다음으로 이전 스티커를 선택했다면 이전에 뗄 수 있는 스티커까지 즉, 만약 현재 스티커의 i가 0이라면 memo[1][i - 1]을 i가 1이라면 memo[0][i - 1]의 값을 가져오게 했습니다. 마지막으로 이전 스티커를 선택하지 않는 경우에는 그 이전까지 뗄 수 있는 스티커까지 즉, memo[0][j - 2], memo[0][j - 1] 중 큰 값을 가져와 이전 스티커를 선.. 2021. 4. 21.
[Java] BOJ 1010번 다리 놓기 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 예를들어 N = 2, M = 5이고 i = 1, j = 1이라면 왼쪽에 한개, 오른쪽에 한개의 사이트이므로 위 이미지와 같이 1개의 연결이 가능합니다. i = 1, j = 5라면 왼쪽에 1개 오른쪽에 5개의 사이트가 있으므로 위 이미지와 같이 5가지 경우로 연결이 가능합니다. 이를 그래프로 표현하면 1 2 3 4 5 1 1 2 3 4 5 가 됩니다. 다음으로 i = 2이고 j = 1일 경우에는 위 그림과 같이 2개의 다리가 설.. 2021. 4. 16.
[Java] BOJ 11052번 카드 구매하기 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 만약 N = 4일 경우는 4장을 뽑았을 때 최대 값이므로 ① 1장을 이미 뽑았을때의 최대값 + P[3] (3장이 있는 카드팩의 비용) ② 2장을 이미 뽑았을때의 최대값 + P[2] (2장이 있는 카드팩의 비용) ③ 3장을 이미 뽑았을때의 최대값 + P[1] (1장이 있는 카드팩의 비용) ④ P[4] (4장이 있는 카드팩의 비용) 중 최대인 값을 선택하면 4장을 뽑았을때의 최대값을 만들 수 있습니다. 코드 import java.io.Bu.. 2021. 4. 15.
[Java] BOJ 14501번 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 DP를 사용하여 해결했습니다. 이때, 상담 완료까지의 기간이 N + 1일 까지라면 N번째날까지 처리가 가능하다는 것을 주의해야 합니다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static int N, ans; public static int[] T = new int[16]; public static int[] P = new int[16]; public sta.. 2021. 4. 14.

티스토리툴바