본문 바로가기

PS831

[자바] 백준 23804 - 골뱅이 찍기 - ㄷ (boj java) 문제 : boj23804 규칙을 찾아 구현을 하면 된다. N=3일 때를 기준으로 규칙을 찾아보자. 위와 같이 규칙을 찾았다면, 규칙에 맞게 반복문을 사용하여 구현만 해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); StringBuilder sb = new StringBuilder(); for.. 2022. 5. 23.
[ABC252] E - Road Reduction (AtCoder Beginner Contest 252 in Java) 문제 : abc252_e 다익스트라 자료구조에 대해 이해를 하고있다면 쉽게 풀 수 있다. 문제에서 제시된 d2+d3+...+dN의 합을 최소화 한다는 말은 즉, 1부터 모든 정점으로의 최단거리를 가지는 N-1개의 edge를 남겨야 한다는 말과 동일하다. 1부터 모든 정점으로의 최단거리는 다익스트라를 돌리면 얻을 수 있고, 다익스트라의 결과는 모든 정점으로의 경로가 존재했다면 N-1개만 남게 된다. 그러므로, 단순히 정점 1부터 시작하는 다익스트라를 구현하고, 이 때 각 정점으로 마지막으로 들어왔던 간선(즉, 각 정점으로 들어온 1부터 최단거리에 해당하는 간선)을 저장해둔 후 그걸 출력해주면 된다. 이 때 'in arbitrary order' 라고 했으므로(랜덤 순서를 뜻한다) 아무 순서로든 출력만 해주면.. 2022. 5. 22.
[ABC252] C - Slot Strategy (AtCoder Beginner Contest 252 in Java) 문제 : abc252_c arr[a][b]는 a라는 수(016(=6+10)으로 눌러야 하므로 16초가 필요하다. arr[1]의 경우엔 0->1->7이므로 7초, arr[2]는 0->2->9이므로 9초... 이런식이다. 이 중 가장 작은 것은 arr[8]로 0->2->6으로 6초가 된다. 이런식으로 arr[a][b]를 구해둘 시 arr[0]~arr[9] 각각의 초를 구하고, 그 중 가장 작은 초를 출력해주면 된다. 코드 : github ... private int getTime(int[] cnt) { int max = 0; for (int i = 0; i < 10; i++) { int calc = i+(cnt[i]-1)*10; max = Math.max(calc, max); } return max; } p.. 2022. 5. 22.
[ABC252] B - Takahashi's Failure (AtCoder Beginner Contest 252 in Java) 문제 : abc252_b N개의 입력값 중 가장 큰 수를 제외한 데이터는 의미가 없다. 결국, N개의 입력값 중 가장 큰 수의 인덱스들이 K개의 입력값 중에 포함된다면 Yes, 아니라면 No를 출력해주면 되는 문제이다. 따라서 내 경우엔 N개를 입력받으면서 max 값을 찾는다. 이 때 새로운 max값이 나타난다면 HashSet을 초기화하고, max값과 동일한값이 나타날 시 HashSet에 추가하는 식으로 진행했다. 이후 K개를 입력받으면서 HashSet에 있는지만 판단해줬다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int k = nextInt(); HashSet hs = new HashSet(); int .. 2022. 5. 22.
[ABC252] A - ASCII code (AtCoder Beginner Contest 252 in Java) 문제 : abc252_a 아스키코드가 int로 주어지면 이걸 문자로 변경해서 출력해주면 된다. 따라서 단순히 입력된 int를 char로 캐스팅만 해주면 된다. 코드 : github ... private void solution() throws Exception { System.out.println((char)nextInt()); } ... 2022. 5. 22.
[자바] 백준 17271 - 리그 오브 레전설 (Small) (boj java) 문제 : boj17271 다음의 dp식을 사용하면 구할 수 있다. dp[0] = 1로 시작하고, i를 1부터 n까지 증가시키면서 dp[1]부터 dp[n]까지 위의 식을 적용해 계산해주면 된다. dp[i]는 i시간이 있을 때의 경우의 수이다. dp[i-1]은 이전의 경우의 수에 A 기술을 쓰는 경우, dp[i-b]는 이전의 경우의 수에 B 기술을 쓰는 경우를 의미한다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static final int MOD = 1000000007; private void solu.. 2022. 5. 22.
[자바] 백준 14579 - 덧셈과 곱셈 (boj java) 문제 : boj14579 f(n)를 1부터 n까지를 합친 삼각수라고 하자. 그럼 f(a)*f(a+1)*...*f(b)의 값을 구하는 문제이다. b-a가 최악의 경우라도 999이므로, 일단 f(a)*f(a+1)*...*f(b) 자체는 O(999)로 가능하다. 그럼 f(a)만 빠르게 구할 수 있다면 문제없이 시간 내에 답을 구할 수 있다. 여러 방법이 있을 것인데, 사실 최대 f(1000)까지만 구할 수 있으면 되므로 매번 반복문을 통해 직접 구해줘도 시간내에 통과는 가능하다. 아니면 이하의 등차수열 합 공식을 사용해서 f(n)을 구해도 된다. 이하 코드는 일단 f(a)를 구한 후 거기에 a+1, a+2, ... ,b를 순차적으로 더하면서 곱해줬다. 코드 : github import java.io.Buffe.. 2022. 5. 21.
[자바] 백준 17212 - 달나라 토끼를 위한 구매대금 지불 도우미 (boj java) 문제 : boj17212 N을 1,2,5,7원들을 최소한으로 사용한 합으로 나타내야 하는 문제이다. dp로 쉽게 풀 수 있다. 점화식은 다음과 같다. dp[i]는 i원을 표현하기 위해 필요한 1,2,5,7원 동전의 최소 개수이다. dp[0] = 0을 base condition으로 둔다면 위의 점화식을 통해 N이하의 모든 값에 대해 최소 개수를 구할 수 있다. 답은 dp[n]이 될 것이다. 말로 표현하자면 "i원(dp[i])을 표현하기 위한 최소개수는 i-1원의 최소개수, i-2원의 최소개수, i-5원의 최소개수, i-7원의 최소개수 중 가장 작은 회수에다가 현재의 동전 1개를 추가한(+1) 개수이다." 코드 : github import java.io.BufferedReader; import java.io.. 2022. 5. 20.
[자바] 백준 1897 - 토달기 (boj java) 문제 : boj1897 문제에서 제시된 로직대로 진행한다면, 항상 L 길이의 단어는 L+1 길이의 단어가 된다. 또한 이 때, L 길이의 단어에 있는 각 문자의 순서는 L+1 길이의 단어에서 나타나는 문자의 순서와 동일하면서, 딱 하나의 문자만 추가될 것이다. 그렇다면 현재 L길이의 단어를 보고 있을 때, L+1 길이의 단어들 중 이동 가능한 문자로 진행을 하는걸 더이상 진행할 수 없을때까지 해보면 될 것이다. 즉, 그렇게 안생겼지만 bfs나 dfs로 풀면 된다. 간선은 [L 길이의 문자 A] -> [A와 문자 순서까지 생각했을 때, 1개의 문자만 추가된 문자 B] 와 같이 생성하면 될 것이다. 미리 입력을 받으면서 글자의 길이에 따라 나누어두면 훨씬 효율적으로 진행할 수 있다. 또한 String이므로 .. 2022. 5. 20.
[자바] 백준 1010 - 다리 놓기 (boj java) 문제 : boj1010 해설은 다음과 같다! 결론은 mCn을 구하면 된다. 코드에서 n = Math.min(n, m-n)은 mCn = mCm-n를 코드로 나타낸 것이다. 일단 연산 도중에 long의 범위를 넘어갈 수 있다. 간단하게는 코드처럼 BigInteger로 처리하면 되고, 사실 n과 m이 그리 크지 않으므로 오차만 적당히 조정해주면 double로 연산해도 통과할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.StringTokenizer; public class Main { private void solution() .. 2022. 5. 20.

티스토리툴바