본문 바로가기

백준756

백준 2312 자바 - 수 복원하기 (BOJ 2312 JAVA) 문제 : boj2312 오랜만에 1분컷으로 푼 것 같다. 소인수분해의 결과는 결국 전부 소수가 될테니 미리 에라토스테네스의 체로 소수를 구해두고 수행하면 더 효율적이긴 하다. 하지만 N이 최대 100000이므로 2부터 N까지의 모든 수로 직접 나눠봐도 O(100000)밖에 안나온다. 따라서 그냥 brute force로 직접 나눠보면 쉽게 답을 구할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamRe.. 2022. 3. 3.
백준 3711 자바 - 학번 (BOJ 3711 JAVA) 문제 : boj3711 g가 최대 300밖에 안되므로 모든 경우를 살펴봐도 O(G^2) 수준이라 브루트포스로 진행해도 무리없이 풀 수 있다. 즉, 1부터 시작해서 수를 점차 키워가면서 모든 값들을 실제로 나눠보고 그 나머지를 체크하면 된다. 이 때 주의점은 중복 체크라고 하면 일반적으로 해시셋을 쉽게 떠올릴텐데, 자바 한정으로 이 문제에서는 해시셋 사용 시 메모리 초과가 날 수 있다. 따라서 배열을 이용해 체크해주면 쉽게 통과할 수 있다. 내 경우엔 각 TC마다 체크용 배열을 초기화하고, 현재 나눠볼 값을 K라 할 때 메모리를 최대한 아끼기 위해 K에 따라서는 매번 초기화하지 않고 해당 K값을 기입했다. 코드 : github import java.io.BufferedReader; import java.i.. 2022. 3. 2.
백준 23394 자바 - Haja Ordenação (BOJ 23394 JAVA) 문제 : boj23394 Brute force로 생각하기 쉽지만, 사실 이 경우 10^5C2 만큼 판단해야 할 것이므로 시간내에 통과할 수 없다. 아이디어만 잘 떠올린다면 아주 간단하게 풀 수 있다. 사실 동일한 색상 2개를 고르고 교환하는 부분을 직접 할 필요가 없다. 중요한건 최종적으로 정렬된 순서로 만들 수 있냐이므로, 처음 입력으로 들어왔던 색상의 순서와 시퀀스만 가지고 정렬한 순서의 색상이 동일하다면 실제 색상 2개를 고르고 서로 교환하는 부분은 어떻게든 가능할테니 대충 퉁칠 수 있는 부분이 된다. 예를들어 예제 입력1과 2는 다음과 같다. 처음 입력으로 들어온 색상과, 시퀀스를 기준으로 정렬된 색상의 순서가 서로 다르다면 N, 동일하다면 Y를 출력해주면 된다. 코드 : github import.. 2022. 3. 1.
백준 2729 자바 - 이진수 덧셈 (BOJ 2729 JAVA) 문제 : boj2729 문제에 제시된대로 실제로 덧셈을 진행해주면 된다! 즉 문제에 나온대로 구현하면 풀 수 있다. 주의점은 입력은 0으로 시작할 수 있는데, 출력은 앞에 0이 붙으면 안된다는 점이다. 즉, '000001 00010' 이런 입력이 들어올 수 있고, 답은 '11' 로 앞의 0들을 출력하면 안된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = n.. 2022. 2. 28.
백준 2947 자바 - 나무 조각 (BOJ 2947 JAVA) 문제 : boj2947 문제에 나온대로 구현만 하면 되는 문제이다. 혹시 구현이 힘들다면 논리적으로 생각하며 어떻게 짜야 주어진 동작이 수행 가능할지 공책에 그려보거나 하면서 구현해 보자. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int[] arr = new in.. 2022. 2. 27.
백준 14729 자바 - 칠무해 (BOJ 14729 JAVA) 문제 : boj14729 문제 자체는 단순히 모두 입력받은 후 오름차순으로 정렬해서 처음 7개만 출력하면 되는 아주 간단한 문제이다. 다만 생각할 부분이 좀 있는데, 애초에 스페셜 저지 문제가 아니므로(별도의 채점 로직 없이 단순히 입력을 주고 출력 나온걸 정답과 비교하는 형태) 무조건 입력받은 형태 그대로 출력해야 한다. 그렇다면 사실 String 그대로 받고 비교하는게 맞긴하다. 왜냐하면 무조건 소수점 3자리까지 입력으로 들어온다고 조건을 주지 않았기 때문이다. 하지만 이 경우 자바로는 String으로 N개를 입력받는 것 자체가 메모리 초과가 나게 된다. 결론적으로 정석대로(String 그대로 받기) 자바로 풀기 위해서는 모두 입력받고 정렬하면 안되고, 별도로 가장 낮은 값 7개를 찾는 로직을 세워야.. 2022. 2. 26.
백준 11507 자바 - 카드셋트 (BOJ 11507 JAVA) 문제 : boj11507 1. 3글자씩 잘라서 각각의 카드를 판단할 수 있어야 함. 길이가 일정하므로 그냥 character 기준으로 3개씩 잘라내면 된다. 2. 똑같은 카드가 존재하는지 판단 '1'의 문자열을 가지고 HashSet을 사용하면 쉽게 동일 카드가 존재하는지 확인할 수 있다. 3. 얼마나 많은 카드를 잃어버렸는지 판단 '1'의 문자열에서 0번 인덱스의 문자(character)를 가지고 카운팅하면 된다. 즉, 첫번째 문자가 각각 P, K, H, T인 것의 개수를 센다. 이후 13-P개수, 13-K개수, 13-H개수, 13-T개수를 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; impor.. 2022. 2. 25.
백준 20115 자바 - 에너지 드링크 (BOJ 20115 JAVA) 문제 : boj20115 어떻게 해야 최대치가 될까? '/2'를 통해 줄어드는 양을 최소화 하면 된다. 그렇다면 일단 합친 값에 대해 추가로 '/2' 연산을 하면 안된다는 점을 알 수 있다. 예를들어 A, B, C가 있을 때 A에 B를 부어서 A가 A+B/2 가 됬다 해보자. 이 용액을 추가로 C에 부어버린다면 C = C + A/2 + B/4가 되는 셈이다. 즉 이미 합쳐진 용액은 더이상 건들지 않는것이 이득이다. 그럼 N개의 용액 중 1개에다가 나머지를 전부 부어버리는 것이 이득임을 알 수 있고, 전체 수치가 최대가 되려면 가장 큰 값을 가지는 용액에다가 나머지 전부를 부어야 함을 알 수 있다. 따라서 단순히 매번 입력을 받으면서 그 중 max 값을 찾고, 모든 용액을 더한다(sum). 최종적으로 답은.. 2022. 2. 24.
백준 16936 자바 - 나3곱2 (BOJ 16936 JAVA) 문제 : boj16936 난이도 기여 멘트들을 보니 많은 분들이 ad hoc으로 보고 수학적으로 푼 것 같다. 3의 차수라는 내용이 많이 나오던데 솔직히 뭔지 잘 모르겠다 ㅋㅋ. 내 경우엔 수학적으로 잘 모르겠으니 그냥 무식하게 풀었다. 각 수를 하나의 정점으로 치고, 방향 그래프를 만든다. 만약 두 수 X, Y가 있고 X*2 == Y 혹은 X/3 == Y 라면 X->Y 처럼 X에서 Y로 가는 간선을 만든다. 예를들어 '예제 입력 1'에 대한 방향 그래프는 다음과 같다. 이렇게 모든 쌍에 대해 간선을 만들고 (모든 쌍이라고 해봐야 100x100개 뿐임), 모든 정점에서 출발해서 DFS를 돌린다. 어떠한 지점에서 DFS를 통해 모든 정점에 갈 수 있다면 해당 루트를 출력해주면 된다. 여기서 좀 더 효율적으.. 2022. 2. 23.
백준 10817 파이썬 - 세 수 (BOJ 10817 Python) 문제 : boj10817 변수가 3개밖에 안되므로, 조건문만 여러개 사용해도 쉽게 풀 수 있다. 하지만 왠지 한줄로 처리하고 싶었다. input()을 split해서 list로 변환 후, 정렬하고 2번째 인덱스의 값을 출력했다. 그럼 2번째로 큰 수가 출력된다. 코드 : github print(sorted(list(map(int, input().split())))[1]) 2022. 2. 23.

티스토리툴바