밤이 블로그

* 문제 https://www.acmicpc.net/problem/1003 * 풀이https://github.com/stack07142/BOJ/blob/master/BOJ%231003_FibonacciCount/src/Main.kt var dp = Array(41) { Node() } fun main(args: Array) { var T = readLine()!!.toInt() while (T-- > 0) { val N = readLine()!!.toInt() fibonacci(N) println("${dp[N].count0} ${dp[N].count1}") } } fun fibonacci(n: Int): Node { if (dp[n].num != -1) { return dp[n] } when (n) {..

BOJ#11049 행렬 곱셈 순서 * 문제https://www.acmicpc.net/problem/11049 * 풀이비슷한 문제 : 파일 합치기 https://www.acmicpc.net/problem/11066 행렬은 결합법칙이 성립합니다. (AB)C = A(BC)그러나 순서에 따라 곱셈 횟수는 달라집니다. 문제 풀이 방식은 파일 합치기 문제와 동일합니다. dp[start][end] = min(dp[start][end], dp[start][k] + dp[k+1][j] + (d_start * d_k+1 * d_end+1)), i

BOJ#1509 팰린드롬 분할 * 문제https://www.acmicpc.net/problem/1509 * 풀이- Manacher 알고리즘을 통해 임의의 범위의 문자열이 팰린드롬인지 구한다. - dp[i] : 0 ~ i 범위의 문자열을 팰린드롬 분할할 때 최소 분할 수 j ~ i 범위 문자열이 팰린드롬일 때, dp[i] = min(dp[i], dp[j-1] + 1)(여기서 j는 0 부터 i 까지) dp[0] = 1이고 -> dp[1] -> dp[2] -> ... -> dp[N-1]을 차례대로 구한다 * 나의 코드https://github.com/stack07142/BOJ/blob/d4b527b666ba54f7f53c1128f5a1523cb261d2b9/BOJ%231509/src/Main.java impo..

BOJ#2352 반도체 설계 * 문제https://www.acmicpc.net/problem/2352 * 풀이 LIS 기본 문제입니다. LIS 설명http://stack07142.tistory.com/56 비슷한 문제들http://stack07142.tistory.com/102http://stack07142.tistory.com/103http://stack07142.tistory.com/287 * 나의 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Mai..

BOJ#1495 기타리스트 * 문제https://www.acmicpc.net/problem/1495 * 풀이dp[idx][volume] : N번째 곡일때, volume 가능 여부(boolean) * 나의 코드https://github.com/stack07142/BOJ/blob/b5664bd70b97831cf6d21fa7d0c37919da9508ce/BOJ%231495/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N, S, M; static int..

BOJ#2631 줄세우기 * 문제https://www.acmicpc.net/problem/2631 * 풀이일단 [4, 1, 2, 3, 5]인 경우의 문제를 손으로 풀어봅시다.거의 대부분 4를 3뒤로 옮겨서 한번만에 문제를 푸셨을 것입니다. 위 과정을 조금 더 상세하게 써보면 1. 수열에서 증가하는 가장 긴 부분 수열을 구하고 (이것들은 움직이지 않음)[4, 1, 2, 3, 5] 나머지 숫자를 적절한 자리로 이동시키면 옮겨지는 아이의 수를 최소로 하면서 줄을 세울 수 있습니다.[4, 1, 2, 3, 5] -> [1, 2, 3, 4, 5] 여기서 우리는 횟수만 구하면 되므로전체 길이 - LIS(Longest Increasing Subsequence) 길이 = 아이의 최소 이동 횟수 = 원하는 답 저는 LIS..

BOJ#2014 소수의 곱 * 문제https://www.acmicpc.net/problem/2014 * 풀이어려운 문제입니다. K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자.예를 들어 세 소수가 2, 5, 7이었다면, 이러한 곱들을 오름차순으로 나타내 보면, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 등이 된다. 즉, 주어진 소수가 [2, 5, 7]일 때2, 5, 7만을 약수로 갖는 숫자들 중 N 번째 숫자를 구하여라. 이 문제는 다음과 같은 알고리즘으로 해결을 할 수 있습니다. 1. 주어진 소수를 배열에 저장한다. 2. 주어진 소수를 PriorityQueue에 add 한다. 3. 아래 과정을 N-1 번 반복(loop) - Prio..

BOJ#10164 격자상의 경로 * 문제https://www.acmicpc.net/problem/10164 * 풀이카카오 블라인드 채용 - 1차 테스트의 모의 테스트에 나온 문제와 유사합니다. 점화식은 간단하게 dp[row][col] = dp[row-1][col] + dp[row][col-1] 임을 알 수 있습니다. 단, K가 0이 아닌 경우 경유지가 1개 있는 것이므로이 경우 시작점->경유지, 경유지->도착점의 경우의 수를 각각 구한 뒤 곱해주면 원하는 답을 얻을 수 있습니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/4cccafbf34e20c197249ac96c20b33f15e644bb1/BOJ%2310164/src/Main.java import java.i..

BOJ#1904 01타일 * 문제https://www.acmicpc.net/problem/1904 * 풀이수열은 끝이 1 또는 00인 2가지 경우로 나눌 수 있습니다.따라서 dp 점화식은 dp[i] = dp[i-1] + dp[i-2] * 나의 코드https://github.com/stack07142/BOJ/blob/a028fa1300ba4112e41be95b11d5daed4b71e8b8/BOJ%231904/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static final int MOD = 15746; static int[]..

BOJ#11051 이항 계수 2 * 문제https://www.acmicpc.net/problem/11051 * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%2311051/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static final int MOD = 10007; static int[][] dp = new int[1001][1001]; public static void main(String[] args) th..