본문 바로가기

BOJ749

백준 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.
백준 11508 자바 - 2+1 세일 (BOJ 11508 JAVA) 문제 : boj11508 1. 어떻게 최소 비용을 만들 수 있을까? 어차피 중복해서 물건을 구매할 수 없고, 모든 물건을 구매해야 하므로 N개의 물건에 대해 'N/3(내림)'개의 물건만을 2+1 세일로 가격을 빼낼 수 있다. 이걸 변경할 방법이 없으므로, 결국 최대한 비싼 물건을 세일로 빼내는 것이 최소 비용을 만들 수 있는 방법이다. 이 때 특정 3개의 문제를 골랐을 때 이 중 가장 싼 물건의 가격이 빠지는 것이고, 이 '가장 싼 물건'이 최대한 비싼 물건일수록 이득이므로 결국 비싼 물건들부터 고르는 것 말고는 최소 비용을 만들 수 있는 방법이 없다. 즉, 문제 설명에서 나온 7개의 유제품 '10, 9, 4, 2, 6, 4, 3'을 봐보자. 문제에서는 위의 표처럼 그룹지었지만, 세일로 빠지는 가격을 늘.. 2022. 2. 22.
백준 11468 자바 - Concatenation (BOJ 11468 JAVA) 문제 : boj11468 1. 우선 모든 경우의 수를 생각해보자. 예제 입력 1의 cat과 dog를 봐보자. 나올 수 있는 모든 경우는 다음과 같다. (cg, cog, cdog, cag, caog, cadog, catg, catog, catdog의 9가지) 이와같이 A와 B가 입력으로 들어온다면, 모든 경우의 수는 [A의 문자 수 x B의 문자 수] 임을 알 수 있다. 2. 그럼 언제 중복된 경우가 발생할까? bbb와 bzz를 확인해보자. 이와 같이 동일한 문자가 존재하는 경우 중복값이 발생한다. 다만 이 때, A 단어의 맨 앞 문자는 무조건 들어가야 하고(non-empty prefix), B 문자의 맨 뒤 글자도 무조건 들어가야 하므로(non-empty suffix) A 문자의 맨 첫문자와, B 문자의.. 2022. 2. 21.
백준 16678 자바 - 모독 (BOJ 16678 JAVA) 문제 : boj16678 1. 문제 이해 결국 단 1번의 Defile로 모두 박탈시키려면 모든 의원의 명예를 1부터 차츰차츰 상승하는 계단형식으로 만들면 된다. 즉, 모든 의원의 명예가 낮은 명예부터 봤을 때 2이상 차이가 나지 않게 하면 된고, 이렇게 만들 때 최소한만 감소시켜서 진행해야 한다. 2. 문제 풀이 1부터 n까지 확인하면서 해당 값을 한명씩 무조건 가지도록 명예를 깎는다면 모든 명예값이 2이상 차이나지 않을 수 있다. 단순히 생각해도 더 낮은 숫자를 만들기 위해서는 애초에 명예가 낮은 의원의 명예를 깎는것이 더 최소한의 횟수로 만들 수 있을 것이다. 따라서 우선 입력으로 들어온 값을 오름차순으로 정렬해보자. 그리고 1부터 1개씩 증가시키며 해당 값에 한명 이상 매칭시켜보자. 예를들어 '예제.. 2022. 2. 21.
백준 18917 자바 - 수열과 쿼리 38 (BOJ 18917 JAVA) 문제 : boj18917 제거 연산이 '항상 A에 x가 있는 쿼리만 주어진다' 라는 조건이 있으므로 상당히 간단해지는 문제이다. 애초에 뭐 가장 앞에 있는걸 제거한다는 부분도 딱히 의미가 없다. 아무튼 있는 값에 대해서만 제거가 되므로 편하게 할 수 있다. 1. 모든 원소를 더한 값 sum과 같이 변수를 하나 두고 1 x 형태의 연산이 들어올 때 더해두고, 2 x 형태의 연산이 들어올 때 빼두면 된다. 2. 모든 원소를 XOR한 값 이게 좀 어려울 수 있다. 일단 1 x 형태의 연산은 그냥 XOR을 하면 된다. ('^' 연산)2 x 형태가 문제인데, 사실 이것도 그냥 XOR을 하면 된다. 왜냐면 어떠한 수 n에 대해 n^n = 0 이다. 즉 자기 자신을 빼내는 것 역시 XOR로 동일한 수를 진행하면 되는.. 2022. 2. 20.
백준 4351 자바 - Hay Points (BOJ 4351 JAVA) 문제 : boj4351 String으로 되어 있는 문자열과, 해당 항목에 대한 int를 저장할 수 있어야 한다. HashMap을 사용하면 효율적으로 저장하고, 찾을 수 있다. m개의 단어와 숫자를 받아 HashMap에 단어를 key, 숫자를 value로 저장한다. 그리고 n개를 입력받으면서 띄어쓰기를 기준으로 나누어 HashMap에 해당 단어가 있다면 점수를 더해나가면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { private void solution() throws Exception { BufferedReader br = new Bu.. 2022. 2. 19.
백준 18294 자바 - Biodiversity (BOJ 18294 JAVA) 문제 : boj18294 1. 우선 각 String마다 카운팅 할 수 있어야 한다. HashMap을 사용하면 편하게 할 수 있다. 2. 매번 각 String을 카운팅하면서, 그 중 현재까지 가장 큰 값과 가장 큰 값을 가지는 동물의 이름을 따로 저장해둔다. (혹은 마지막에 해시맵에서 key들을 뽑아낸 후 확인해도 된다.) 3. 다른 동물들의 합보다 어떠한 동물이 더 많으려면 (int)N/2보다 더 많은 수를 가져야 한다. (홀수라도 5/2 = 2 이므로 3 이상이면 더 많은것이다.) 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { private .. 2022. 2. 18.

티스토리툴바