본문 바로가기

BOJ749

[자바] 백준 2559 - 수열 (boj java) 문제 : boj2559 이하 설명에서 arr[i]는 입력으로 주어진 i번째 수를 뜻한다. 총 세 가지 방식으로 풀이를 진행한다. 1. 누적합 (prefix sum) prefix sum (누적합)을 미리 구해둬보자. 누적합 배열을 sumArr이라고 하고, sumArr[i]는 arr[1]+arr[2]+...+arr[i] 라고 하자. 그렇다면 sumArr[i] = arr[i] + sumArr[i-1]이 될 것이다. 이렇게 누적합 배열을 구해둔다면, 이후 아래의 공식을 통해 각각 O(1)로 arr[i]부터 이전 K개의 합을 구할 수 있다. 따라서 O(N)으로 답을 구할 수 있다. 코드1 : github - prefix sum import java.io.BufferedReader; import java.io.In.. 2022. 5. 27.
[자바] 백준 1671 - 상어의 저녁식사 (boj java) 문제 : boj1671 문제에서 제시된 상황이 그래프로 표현 가능한 경우 그래프로 바꿔서 생각해보는 것이 이득인 경우가 많다. 이 문제의 경우에도 주어진건 상어의 크기, 속도, 지능으로 3개나 되지만, 사실 그래프의 간선으로 생각해본다면 값이야 어떻든 조건을 만족한 경우 그냥 방향이 있는 간선 하나가 추가될 뿐이다. 예시 입력 1을 그려보면 다음과 같다. 간선은 [먹는쪽 -> 먹히는쪽]으로 연결할 것이다. 5 4 5 5 10 10 8 5 7 10 8 7 7 8 10 3 그럼 동일 정점을 좌우로 둬서 다음과 같이도 그려볼 수 있다. 결국 최대한 많이 잡아먹으면 남아 있는 수가 최소가 되므로, 최대유량 문제인데 이분그래프 이므로 이분매칭을 사용해서 좌측의 상어가 우측의 상어를 먹는다고 생각해보자. 그리고 좌.. 2022. 5. 26.
[자바] 백준 11660 - 구간 합 구하기 5 (boj java) 문제 : boj11660 prefix sum을 이용하는 문제이다. 1차원 배열에 대해 prefix sum을 계산해두면 1차원 배열의 모든 구간에 대한 구간합을 O(1)로 구할 수 있다. 따라서 모든 행에 포함된 열에 대해 행의 개수만큼 prefix sum을 계산해둔다면, O(MN)으로 문제를 풀 수 있다. 이렇게 짠 코드는 여기(github)에 있다. 이하 풀이는 2차원 prefix sum을 사용한 풀이이다. 2차원 배열에 대해 prefix sum을 유지한다면 O(M)으로도 가능하다. arr[a][b]를 (1, 1)부터 (a, b) 까지의 합이라고 정의하자. 그럼 arr[a][b] = '[a. b]의 값' + arr[a-1][j] + arr[a][b-1] - arr[a-1][b-1] 이라고 할 수 있다... 2022. 5. 26.
[자바] 백준 21939 - 문제 추천 시스템 Version 1 (boj java) 문제 : boj21939 우선 한글적으로 좀 해맬만한 부분이 있어서 그것부터 써보겠다(제가 그래서 틀렸었단 얘깁니다 ㅠ). add의 '(추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)' 라는 설명과 solved의 '(추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)' 라는 설명 때문이었다. 결론적으로 '추천 문제 리스트'는 처음 N개의 입력만을 뜻한다. 그리고 '이전에 추천 문제 리스트에 있던 문제 번호'라는 말은 즉, N개에 존재했었으나 solved로 제거된 경우엔 add로 동일한 번호가 들어올 수 있다는 말이었다. 마찬가지로 solved의 설명 또한 해석하자면 결국 N개에 존재했던 녀석들만 .. 2022. 5. 25.
[자바] 백준 18221 - 교수님 저는 취업할래요 (boj java) 문제 : boj18221 문제 제목이 상당히 무섭고, 지문이 길긴 하지만 정리해보면 결국 알아야 하는건 어렵지 않다. 알아내야 하는걸 정리해보자. 1. 성규가 앉은 위치의 좌표 2. 교수님이 앉은 위치의 좌표 3. '1'과 '2'의 거리가 5이상인지 4. '1'과 '2'로 만들어지는 직사각형 혹은 선 위에 몇 명의 학생이 있는지 위와 같이 알 수 있으면 풀 수 있다. '1'과 '2'는 입력을 받으면서 알 수 있다. '3'은 문제에서 제시된 공식으로 알 수 있다. 다만, double로 처리하는건 항상 소수점 오차의 문제가 생길 가능성이 있다. 따라서 아래와 같이 공식을 바꿔서 int내에서 처리가 되도록 하자. 이하의 조건을 만족하지 않는다면 바로 0을 출력하고 종료하면 된다. '4'의 경우엔 결국 직사각형.. 2022. 5. 24.
[자바] 백준 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.
[자바] 백준 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.

티스토리툴바