본문 바로가기

백준756

[자바] 백준 5591 - 最大の和 (boj java) 문제 : boj5591 n개의 데이터에서 연속된 k개의 합이 최대인 지점을 찾으면 된다. 두 가지 정도로 해볼 수 있다. 이하 예시는 다음 입력을 이용해 설명하겠다. 5 3 2 5 -4 10 3 1. 슬라이딩 윈도우 처음 k개의 합을 구한다(A). k개의 윈도우를 옆으로 옮겨다니듯이 생각하면 된다. 그럼 윈도우를 우측으로 한 칸 이동한다면, 직전 윈도우 위치의 첫번째 위치의 값을 빼고 이번에 새로 추가된 값을 더해주면 된다. 이런식으로 이동하면서 최대값을 구하면 된다. O(N) 2. prefix sum 입력을 받을 때 미리 누적합을 계산해둔다. 그렇다면 i번 인덱스에서 이전 k개 원소들의 합은 arr[i]-arr[i-k]가 된다. 이걸 i를 k부터(그래야 i-k가 0 미만으로 안내려갈테니) n까지 증가시.. 2022. 5. 12.
[자바] 백준 11880 - 개미 (boj java) 문제 : boj11880 문제에서 제시된 직육면체에서 A에서 B로 가는 최단 거리를 어떻게 구할 수 있을까? 직육면체를 전개해서 살펴보면 어렵지 않게 피타고라스의 정리만 가지고 최단거리의 길이를 구해낼 수 있다. 다만 이 문제에서는 '서로 반대편에 위치한 A, B점까지의 최단 거리' 라고 했으므로 A, B점은 임의로 변경해도 된다고 볼 수 있다(정확힌 틀려보고 알았다 ㅠㅠ). 그렇다면 그냥 3개의 변의 길이가 주어졌을 때, 위의 x^2+(y+z)^2이 최단이 되는 값을 찾으면 된다(x,y,z에 각각 a,b,c를 넣었을 때). 즉, 이하의 3가지 중 최단 거리를 찾으면 된다. a,b,c 3가지 중 2가지를 택하므로 3C2 = 3가지 경우를 모두 살펴봐서 최단거리를 구하면 된다. 다만 이 경우 직관적으로 x.. 2022. 5. 11.
[자바] 백준 1110 - 더하기 사이클 (boj java) 문제 : boj1110 문제에서 요구하는 대로 구현을 하면 된다. 과정을 정리하면 다음과 같다. 제시된 대로 시뮬레이션 하면서 몇 회 진행됬는지 세기만 하면 되므로 별다른 알고리즘적인 지식은 필요없다. 일반적으로 숫자 그 자체로 연산해서 구하는 방법과, 문자열로 보고 구하는 방법이 있을 것이다. 이하 코드1과 코드2에 두 가지 방법을 모두 구현했으니 코드를 참고해서 구현해보자. 코드1 (정수로 구하기) : github import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { private voi.. 2022. 5. 11.
[자바] 백준 2936 - 채식주의자 (boj java) 문제 : boj2936 우선 이 문제를 풀기위한 가장 기본이 되는 개념부터 알아야 한다. 초등학교나 언젠가 배웠을테지만 까먹었을 수도 있으므로! 삼각형의 넓이는 한 변만 x나 y축에 평행하다면, 평행한 면의 길이 w와, 그와 수직인 높이 h에 대해 w*h/2 로 구할 수 있다. 즉, 아래와 같은 삼각형 3개(검정, 주황, 초록)는 w가 셋 다 동일하고 h도 동일하므로 다른 것 처럼 생겼지만 사실 넓이는 전부 동일하다. 위의 개념만 잘 알고 있다면 문제에서 제시된 삼각형의 어느 지점의 한 점이 주어지더라도 두 구역의 넓이를 동일하게 하는 넓이를 구할 수 있다. 예를들어 아래처럼 주황선으로 나뉜 구역의 넓이는 다음과 같이 w와 h를 잡으면 된다. 이 문제의 경우 입력에 따라 다양한 경우가 존재한다. 따라서 .. 2022. 5. 10.
[자바] 백준 8892 - 팰린드롬 (boj java) 문제 : boj8892 각 테스트케이스마다 k가 최대 100개이므로, 모든 쌍을 보더라도 O(T x 100^2)번에 가능하다. 또한 모든 단어의 길이의 합은 10,000이하라고 했으므로, 단어 길이의 합을 L이라 할 때 팰린드롬인지 확인하는 로직이 O(L)짜리 로직이라 하더라도 O(TL x 100^2)으로 가능하다. 또한 팰린드롬인 값이 하나라도 있다면 거기서 종료하면 되므로, 대강 모든 경우를 봐도 시간내에 통과 가능할 것임을 예상할 수 있다. 우선 문자열 S가 팰린드롬인지 확인하는 가장 간단한 방법은, |S/2|까지 인덱스를 증가하면서 앞과 뒤의 문자를 확인하는 것이다. isPalindrome() 함수를 확인해보면 알 수 있다. 그리고 모든 경우를 보는 것은 모든 문자쌍을 만들어보면 된다. 코드의 2.. 2022. 5. 9.
[자바] 백준 2480 - 주사위 세개 (boj java) 문제 : boj2480 셋 다 같은 눈인지, 셋 중 둘이 같은 눈인지, 모두 다른 눈인지 확인만 할 수 있다면 풀 수 있다. if문을 사용해 짜보자! 코드 : github import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffe.. 2022. 5. 9.
[자바] 백준 12981 - 공 포장하기 (boj java) 문제 : boj12981 당연히 3개씩 넣는게 가장 좋으며, 그게 안된다면 2개씩, 그것도 안된다면 1개씩이라도 넣으면 된다. 이건 당연한건데 문제는 박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다는 제약때문에 순서를 잘 정해야 한다. 내 경우 이하의 로직으로 풀었다. 1. 우선 가능한 만큼 모두 다른색으로 3개를 박스에 넣는다. (따라서 정렬 후, 가장 낮은 값을 나머지 2개에서 빼줬다.) 2. 이제 3개씩 넣을 수 있는 방법은 모두 같은 색으로 3개를 넣는 방법 뿐이다. 따라서 남은 2개의 색상은 각각 3개씩 가능한 만큼 넣어준다. 3. '2'에서 남은 공운 1개 아니면 2개일 것이다(3개씩 넣었으므로). 이 때 가능한 경우는 다음과 같다. 3.1 둘다 남은게 0개인 경우 -> 모두 3개.. 2022. 5. 8.
[자바] 백준 19939 - 박 터뜨리기 (boj java) 문제 : boj19939 우선 K개의 바구니에 N개의 공을 나눠 담을 수 있는지 여부부터 확인해보자. 이건 쉽게 1+2+...+k 가 n보다 큰지 확인하면 된다. 등차수열의 합 공식을 사용하면 합을 쉽게 구할 수 있다. 등차수열 합 공식은 다음과 같다(n이 수의 개수, a가 첫 항의 값, l이 n번째 항의 값) 그리고 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 차이가 최소가 되려면 어떻게 해야할지 생각해봐야 한다. 이 경우 직관적으로 k개를 1씩 차이를 내는게 최선임을 알 수 있다. 즉, 1. 1+2+...+K 2. 2+3+...+(K+1) 3. 3+4+...+(K+2) ... 과 같이 증가시키면서 N보다 커지는 순간을 찾으면 최소값을 어디서 구해봐야할지 알 수 있다. (합은 위의 등차수열 .. 2022. 5. 7.
[자바] 백준 22155 - Простая задача (boj java) 문제 : boj22155 구글 번역기를 쓸 수 있다면 풀 수 있다(?). 각 테스트케이스마다 a, b를 입력받는다고 할 때 a가2보다 작고 b가 1보다 작거나, b가 2보다 작고 a가 1보다 작으면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLin.. 2022. 5. 6.
[자바] 백준 24586 - Code Guessing (boj java) 문제 : boj24586 문제의 조건을 만족하는 경우를 직접 생각해보며 (신중히) 찾아보면 된다. 우선 입력으로 들어올 수 있는 문자열의 모든 경우를 살펴보면 아래와 같다. 그럼 각각의 경우에 A가 어떤 값이어야 'uniquely determine the two digits on Bob’s cards'라는 조건에 부합하는지 확인해보면 다음과 같다. 이유는 잘 생각해보면 알 수 있다! 저 경우에만 B를 확정적으로 예상할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static boolean ch.. 2022. 5. 5.

티스토리툴바