밤이 블로그

BOJ#1890 점프 * 문제https://www.acmicpc.net/problem/1890 * 풀이dp + dfs로 풀었습니다.정답 비율에 비해 문제가 굉장히 쉽습니다. N 범위와 경로의 개수 범위(long)만 주의하면 될 것 같습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231890/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[] dRow = {0, 1}; stat..

BOJ#10216 Count Circle Groups * 문제https://www.acmicpc.net/problem/10216 * 풀이주어진 노드들은 결국 disjoint sets를 형성합니다. 따라서 Union-Find 자료구조를 이용해보았습니다. Two sets are said to be disjoint if they have no element in common. (출처 : https://en.wikipedia.org/wiki/Disjoint_sets) 해야 할 일은 3가지입니다. 1. 노드 간 거리 비교 : 거리 비교 시 양변을 제곱하여 비교하였습니다. 2. 비교 결과에 따라 노드를 그룹으로 묶기 : Union-Find 자료구조 사용 3. 그룹 개수 출력하기 : UnionFind Class에 c..

BOJ#1927 최소 힙 * 문제https://www.acmicpc.net/problem/1927 * 풀이- Heap 설명 : http://stack07142.tistory.com/198 - 2가지 방법으로 풀어 보았습니다. 1) 제공되는 PriorityQueue 이용하기 2) Min Heap 구현하기 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231927_MinHeap/src 1) Priority Queue 이용하기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; /** ..

BOJ#1234 크리스마스 트리 * 문제https://www.acmicpc.net/problem/1234 * 풀이dp[N][R][G][B] : 레벨 N에서 장난감이 R, G, B개 남아있을 때 경우의 수 각 레벨에서는 3가지 경우를 탐색합니다. 1) 장난감을 1가지 종류만 쓰는 경우2) 장난감을 2가지 종류를 쓰는 경우 (N % 2 == 0일때)3) 장난감을 3가지 종류를 쓰는 경우 (N % 3 == 0일때) 그리고 각 경우의 수를 구한 뒤 장난감들의 순서도 생각해주어야 합니다. 참고 링크 : https://namu.wiki/w/순열(수학)3. 같은 것이 있는 경우의 순열(동자 순열)[편집]n개 중에 r개를 중복없이 순서에 맞게 뽑는데, n개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 ..

BOJ#2309 일곱 난쟁이 * 문제https://www.acmicpc.net/problem/2309 * 풀이오름차순 정렬 후 순열 -> 문제 조건(합이 100)인 경우 return * 나의 코드 (Kotlin)https://github.com/stack07142/BOJ/blob/master/BOJ%232309/src/Main.kt import java.util.* fun main(args: Array) { val input = Scanner(System.`in`) var numArr = Array(9, { 0 }) for (i in 0..8) { numArr.set(i, input.nextInt()) } numArr.sort() permutaion(numArr, 0) for (i in 0..6) { p..