본문 바로가기

PS831

[자바] 백준 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.
[ABC250] D - 250-like Number (AtCoder Beginner Contest 250 with Java) 문제 : abc250_d 최대 10^18 까지 표현이 가능해야 한다. 이 때 p n || calc < 0) break; cnt++; } } System.out.println(cnt); } ... 2022. 5. 9.
[ABC250] C - Adjacent Swaps (AtCoder Beginner Contest 250 with Java) 문제 : abc250_c 일단 단순히 swap만 하는 거였다면 별 문제가 없었을 것이다. 문제는 매번 swap해서 바뀌는 각 숫자의 위치를 유효한 시간 내에 찾아내야 한다는 점이다. 만약 매번 전체 배열을 순회하며 찾으려 한다면 O(N+QN)만큼(처음 N은 배열 입력받는 부분, QN은 각 쿼리마다 최대 N번 확인해야 하므로) 필요할 것이므로 시간내에 통과할 수 없다. 따라서 배열을 2개 써서 다음과 같이 한번 생각해보자. N이 5인 경우이다. 원래는 위의 저 '값 배열'만 가지고 해야했는데, '위치 기록용 배열'을 추가로 만들었다. B[z]는 값 z의 현재 idx를 나타낸다. 즉, A[B[z]] == z 이다. 이렇게 메모리를 더 써서 배열 하나를 더 두면 swap 시에 다음과 같이 해볼 수 있다. 현재.. 2022. 5. 9.
[ABC250] B - Enlarged Checker Board (AtCoder Beginner Contest 250 with Java) 문제 : abc250_b 패턴을 잘 살펴보면 결국 NxA행, NxB열의 문자열을 출력하면 된다. 그리고, 시작하는 문자가 '.'으로 시작하는게 A줄, 그 다음 '#'으로 시작하는게 A줄... 을 N줄동안 수행하면 된다. 단순 구현문제긴 한데 반복문에 익숙치 않다면 좀 어려울 수 있다. 4중 for문에서 처음 2중은 N과 A, 그 다음 2중은 N과 B라고 생각하면, 코드로는 4중 for문이지만 개념적으로는 2중 for문이 된다. 그럼 좀 더 쉽게 구해볼 수 있다. boolean값을 잘 설정해서 한번 구현해보자. 참고로 이하 코드에서 'i&1==0'은 i가 짝수라면 true, 홀수라면 false 이다(왜 그런지는 짝수와 홀수를 아무 숫자나 2진수로 바꿔보면 알 수 있다.). 'isWhite^swt'에서 '^.. 2022. 5. 9.
[ABC250] A - Adjacent Squares (AtCoder Beginner Contest 250 with Java) 문제 : abc250_a (1, 1)부터 (H, W) 까지의 모든 square 쌍 (h, w) 대해 이하가 만족하는 경우를 카운팅하면 된다. 코드 : github ... private void solution() throws Exception { int h = nextInt(); int w = nextInt(); int r = nextInt(); int c = nextInt(); int cnt = 0; for (int i = 1; i 2022. 5. 9.
[자바] 백준 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.

티스토리툴바