본문 바로가기

백준 문제 풀이

 (161)
[백준 1082번] 방 번호 (C++) https://www.acmicpc.net/problem/1082 방 번호는 무한으로 살 수 있으므로 N = 10이고 최대 값은 50이다. 이 때 모든 경우의 수를 다 해보는 것은 약 10^10으로 10억이상으로 엄청난시간이 걸린다. 중요한 추론은 숫자를 가장 길게 만들어야한다는 것이다. 그리고 91111 보다는 92000이 크고 100000이 더 크다. 즉 가장 비용이 적은 것들을 사용해서 먼저 가장 긴 방번호를 만들어둔 후 각 자리수마다 하나씩 비교하며 더 큰 값을 사용할 수 있을지 검사한다. 이 방법은 N^3 의 시간밖에 소요되지 않는다.  그리고 각 번호의 개수를 배열에 저장해두고 큰 값부터 다음 값이 가능한지 확인한다. 왜 큰 값부터 해야하냐면 만약 작은것부터 시행했을 때는 다음과 같은 문제가 ..
[백준 1033번] 칵테일 (C++) https://www.acmicpc.net/problem/1033 1:3, 4:7 등 여러 비율이 주어지고 결국 이어지는 길목을 똑같이 이어줘야하는 문제이다.   만약 1번 : 2번 = 4 : 72번 : 3번 = 3 : 10 이라하면 1번 : 2번 : 3번이 성립하는데 비율이 다르기 때문에 이것을 통일해줘야한다.2번이 처리해야하는 비율은 3과 7이다. 그렇다면 21로 비율을 맞출 수 있다. 21로 맞추면 1번에는 x3을 해줘야하고 10에는 x7을 해줘야한다. 그렇다면  12 : 21 : 70 이고 이것이 정답이다. 만약  2번:4번 = 5 : 3 이라면 2번은 3,5,7을 갖고있고 이것을 통일해야한다. 문제는 가장 적은 비율을 요구한다. 그러므로 최소공배수를 구해야한다는 것을 알 수 있다.  또한 문제가..
[백준 2138번] 전구와 스위치(C++) https://www.acmicpc.net/problem/2138 여러가지 상황을 시도하고 규칙성을 찾아내는 것이 관건인 문제이다. 관건은 서로 영향을 줄 수 있는 스위치들이 엮여있기 때문에 모든 경우의 수를 해보는 것이 가장 간단하지만 시간초과가 날 것이다. 먼저 서로 영향을 끼치는 관계를 그림으로 나타내보자  무엇을 의미하는지 잘 모르겠다..그러나 일반적으로 어떤 방식을 사용하던 스위치는 결국 켜거나 놔두게 될 것이다. 한번 1번 스위치를 켰다고 가정하자. 그렇다면 1,2번 전구가 켜졌을 것이다.   그리고 이제 2번 스위치를 켤지 말지 결정해보자. 어라? 여기서 1번을 향하고 있는 스위치가 단 한개이다..!즉 1번은 이제 내 마음대로 조절할수가 있게 되었다.  만약 목표로하는 타겟의 1번이 켜져있다..
[백준 2250번] 트리의 높이와 너비 (C++) https://www.acmicpc.net/problem/2250   문제는 이해했을 것이고 어떻게 풀어야할까  먼저 이 문제는 root가 정해져있지 않다. 부모가 없으면 그게 루트이고 들어오는 순서들도 루트부터 레벨순으로 들어오지 않음을 유의하자. 이 문제는 한번 N번 노드가 자리를 잡게 한 후 계속 갱신시켜가면 O(2^N) 이상의 시간이 걸린다. 예를 들어 처음에 root를 1번에 자리시킨다고 하자. 그리고 2번, 3번이 들어올 때 마다 자리를 옮긴다면 마지막 18, 19가 들어올 때도 최적의 자리를 위해 모든 노드를 갱신해야할 뿐더러 그것이 최적의 자리인지도 확실하지 않다. 문제의 조건을 보면 각 노드의 컬럼 사이는 비어있지 않다. 그러므로 문제를 최적의 자리를 찾는다에서 반드시 비워둬야할 자리가 ..
[백준 15824번] 얘 봄에는 캡사이신이 맛있단다 https://www.acmicpc.net/problem/15824 처음에는 DP로 생각했으나 O(N^2) 에서 시간을 더 줄이는 것이 불가능했다. 이 문제는 모든 조합을 구하는 것은 O(2^N - 1) 로 불가능하다. 가장 중요한 추론은 어떠한 조합이든 결국 최댓값과 최솟값만 알면 스코빌지수를 알 수 있는 것이다. 1, 2, 3, 4 가 있을 때1 ,2, 41, 3, 41, 4 스코빌지수는 모두 3이다.  두번째 떠올려야할 아이디어는 위처럼 꼭 모든 조합을 해봐야알 필요는 없다. 사실 이것을 생각해내기가 가장 어려운 것 같다. 당연히 조합을 먼저 구하려고 하는 것이 일반적이기 때문이다. 1, 2, 3이 있다고 하자.3은 최댓값으로 (1, 3), (2, 3), (1, 2, 3) 으로 총 3번의 최댓값이 ..
[백준 2515번] 전시장 (C++) https://www.acmicpc.net/problem/2515 문제는 직관적으로 이해하기 어렵지 않았지만 어떻게 풀어야할지 감이 잘 안오는 문제다. 하지만 N = 30만이므로 완전탐색은 불가능하고 모든 그림을 배치하고 살펴보는 DFS, BFS 방식도 불가능하다고 판단했다. Greedy 탐욕법탐욕법은 어떨까? 그림의 가격순으로 정렬하고 가격이 높은 것부터 배치하고 다음 그림을 배치할 수 있다면 배치하는 방식을 사용하면 어떨까. 그리디를 사용하기 위해서는 두가지 조건을 만족해야한다.1. 탐욕 선택 조건: 앞에서 탐욕 선택한 값이 이후의 값에 영향을 주어선 안된다.2. 최적 부분 조건: 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다. 이 문제에서 탐욕 선택 조건에서 문제가 있다. 만약 100의 ..
[백준 1633번] 최고의 팀 만들기 (C++) https://www.acmicpc.net/problem/1633 1000개 중 30개를 적절히 구하는 것은 1000개중 30개를 뽑는 모든 연산을 진행해야한다. 1000 combination 30 = 2429608192173745103270389838576750719302222606198631438800 이다. 미친시간이 걸리기 때문에 완전탐색은 불가능하다.  탐욕법 (Greedy)그디리하게 접근해보자. 문제 조건처럼 총 30개를 선택하는 건 어려우니 백2, 흑2 총 4팀을 뽑는다고 가정하자.(10, 20), (30, 400), (5, 1000), (100, 10), (40, 40), (15, 30) 이렇게 들어올 때, 흑으로 정렬한다. (100, 10), (40, 400), (30, 40), (15,..
[백준 1484번] 다이어트 (C++) https://www.acmicpc.net/problem/1484 문제를 이해하기 힘들었다. 기억하고 있는 몸무게라니 이게 무슨말인지,, 그런데 질문게시판을 참고하고 문제를 몇번 다시 읽어보니 기억하고 있는 몸무게 = 이전 몸무게 였다. 1. beforeWeight + G = afterWeight2. afterWeight^2 - beforeWeight^2 = G 이 두 식으로 푸는 수학 문제라 생각했는데 여기서 G는 단순 차이가 아니라 새롭게 정의되어 있는 것이었다. 그러니까 1번 식은 잘못되었다. afterWeight는 a, beforeWeight 는 b라 할 때, 2번을 식을보면 G는 반드시 0보다 큰 자연수이기 때문에 a는 반드시 b보다 크다. 그리고 두 수를 선택해서 비교하는 작업은 두포인터가 가..

티스토리툴바