전체 글
-
1149번 RGB거리 / BOJ / acmicpc.net백준 2020. 1. 27. 22:35
문제링크 : https://www.acmicpc.net/problem/1149 제출링크 : https://www.acmicpc.net/source/17183603 i 가 집의 순서, j 가 색깔(RGB)라고 정의하면, 문제에서, 모든 이웃은 같은 색으로 칠할 수 없다. 그리고 i의 이웃은 i-1 과 i+1 이다. 라고 했는대요. 이부분에서 i-1과 i+1을 동시에 고려해야 하는 것으로, 오해를 할 수 있습니다. 주의 깊게 봐야할 부분이 모든 이웃 입니다. 즉, i-1 과 i 번째 집의 색이 다르기만 하면, 조건을 만족 시킬 수 있습니다. 따라서, i+1은 고려하지 않아도, 위의 조건을 만족시킬 수 있습니다. 점화식(Recurrence Relation)은 아래와 같이 만들 수 있습니다. 앞집(i-1)과 색..
-
1003번 피보나치 함수 / BOJ / acmicpc.net백준 2020. 1. 27. 22:19
문제링크 : https://www.acmicpc.net/problem/1003 제출링크 : https://www.acmicpc.net/source/17178118 import java.util.Scanner; /** * 1003번 피보나치 함수 / BAEKJOON ONLINE JUDGE / acmicpc.net * 문제링크 : https://www.acmicpc.net/problem/1003 * 제출링크 : https://www.acmicpc.net/source/17178118 */ public class Main { public void solve() { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int t=0; t
-
13460번 구슬 탈출 2 / BOJ / acmicpc.net백준 2020. 1. 27. 18:39
13460번 구슬 탈출 2 / BOJ / acmicpc.net 문제링크 : https://www.acmicpc.net/problem/13460 답제출 : https://www.acmicpc.net/source/17221215 Java source : https://github.com/skysign/WSAPT/blob/master/acmicpc.net/13460%EB%B2%88%20%EA%B5%AC%EC%8A%AC%20%ED%83%88%EC%B6%9C%202/src/Main.java 다른분들의 풀이를 보면 BFS로 푸신 것 같아서, DFS로 풀이를 만들어 봤습니다. 문제가 까다로운 부분이 몇가지 있어서, 풀기 좀 어려웠습니다. 공이 1개가 아니고 2개 빨간공과 파란공이 있다는 점 두 공을 굴려서, 이동 시..
-
Prefix sum / 누적합, 구간의 합 구하기카테고리 없음 2020. 1. 21. 11:12
N - Slimes /atcoder.jp (https://skysign.tistory.com/170) 문제에서 사용된 알고리즘으로, prefix sum 알고리즘이 있습니다. prefix sum을 활용하면, 1차원 배열이 있다고 할 때, 1차원 배열의 특정 구간 x ~ y 까지의 합을 빠르게 구할 수 있습니다. \begin{aligned} 1 \leq n \leq N \\ a_x \in ( a_1 ... a_n ) \\ a_y \in ( a_1 ... a_n ) \\ 1 \leq x < y \leq N \\ \end{aligned} 자바 코드는 아래와 같습니다. long[] as = new long[N+1]; long[] prefixSum = new long[N+1]; for(int i=1; i
-
N - Slimes / atcoder.jpatcoder.jp 2020. 1. 21. 10:58
문제링크 : https://atcoder.jp/contests/dp/tasks/dp_n 문제해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/9653540 Java source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/N%20-%20Slimes/src/Main.java 여러개의 슬라임을 2개씩 합칠 때, 합치는 비용을 고려해서, 가장 적은 비용으로 합치는 방법을 찾는 문제입니다. 이 문제를 DP가 방식이 아니라, 아주 간단하게 생각해서, 인접한 두수의 합이 최소가 되는 방식으로, 2개의 슬라임을 합처나가면, 최..
-
L - Deque / atcoder.jpatcoder.jp 2020. 1. 18. 11:59
문제링크 : https://atcoder.jp/contests/dp/tasks/dp_l 문제해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/9546944 Java source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/L%20-%20Deque/src/Main.java 리스트가 주어지고, 두 플레이어가, 이 리스트의 가장 앞/뒤 중에 하나를 서로 빼게 됩니다. 플레이어 타로/지로에 따라서, 뺀수는 타로는 X, 지로는 Y에 더하게 되구요, X-Y 값을 찾는 문제입니다. 문제를 풀기에서 앞서서, 타로와 지로가 숫자를..
-
K - Stones / atcoder.jpatcoder.jp 2020. 1. 16. 17:57
문제링크 : https://atcoder.jp/contests/dp/tasks/dp_k 문제해설 : https://jinpyo.kim/EducationalDP-solution Submission 첫버전 : https://atcoder.jp/contests/dp/submissions/9509087 Submission 속도최적화 : https://atcoder.jp/contests/dp/submissions/9543565 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/K%20-%20Stones/src/Main.java K - Stones 문제입니다. 문제 설명이 약간 모호할 수도 있는대, Sample input 1을 가지고 문제를..
-
I - Coins / atcoder.jpatcoder.jp 2020. 1. 13. 13:12
문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_i 문제 해설 : https://jinpyo.kim/EducationalDP-solution https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp https://www.youtube.com/watch?v=jbA8fPaiYtQ Submission : https://atcoder.jp/contests/dp/submissions/9313650 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/I%20-%20Coins/src/Main.j..