본문 바로가기

Problem Solving/백준

 (80)
[백준/C++/ICPC] 4090번 뱀파이어 숫자 오랜만에 골드를 풀어서 그런지 대략 일주일 걸린 것 같다. 처음 문제를 봤을 때는 안에 있는 숫자들을 순열로 뽑아서 나누는 지점을 정해서 브루트포스로 돌리면 답이 나올 것 같았다. 그런데 뱀파이어 숫자가 아닌 수를 입력으로 주는 경우 뱀파이어 숫자이며 input보다 큰 숫자 중 가장 작은 숫자를 출력에서 멘붕이 왔다. 내가 말한 방법은 100% 또 다시 x보다 큰 뱀파이어 숫자를 여러번 찾는 과정에서 시간 초과가 날 것 같았다. (10초라는 후한 시간이 있어 시도해볼까 싶다가 최근 정답률이 너무 떨어져서 신중해졌다.) 오늘 다시 곰곰히 생각해보다 문제를 쪼개보기로 결정하였는데 문제를 나눠보다보니 더 좋은 방법이 떠올랐고 뱀파이어 숫자 구분 함수를 아래와 같이 2개의 문제로 나눴다. 사용한 숫자가 모두 같..
[백준/C++] 2358번 평행선 뭔가 자세히 보다가 결국 x축과 평행한 선의 갯수와 y축과 평행한 선의 갯수를 찾으면 된다는 것을 알게되었다. map에 key값으로 x좌표와 y좌표를 따로 넣고, 같은 key값으로 숫자가 1번 이상 들어가게 된다면 평행한 선의 조건을 충족하므로 map으로 구현하였다. key값만 따로 보관하는 방법을 찾지 못해서 set에 key값을 저장해주었다. #include using namespace std ; set points ; map x_axis, y_axis ; int N, x, y, answer ; int main() { ios::sync_with_stdio(0), cin.tie(0) ; cin >> N ; for(int i = 0 ; i > x >> y ; x_axis[x..
[백준/C++] 23826번 와이파이 문제 설명이 장황한데 결국 첫 줄에 받은 공용와이파이가 manhattan distance( |X1 - X2| + |Y1 - Y2| ) 거리로 특정 방에 영향을 미치고 각 방에 설정된 공유기가 전파에 같은 방법으로 방해를 끼칠 때 가장 전파가 잘 터지는 방을 구하는 문제이다. 모든 방을 둘러보며 모든 공유기가 닿았을 때 미치는 결과를 확인해보아야 하므로 브루트포스로 해결할 수 있겠다는 생각을 하였다. 중간에 미치는 전파가 음수가 되는 실수를 했는데 예제 1번에서 잘 걸러줘 한 번에 성공할 수 있었다. 예제가 친절한 문제다.. /** * @file 25826.cpp * @author fpqpsxh * @date 2023-01-18 **/ #include using namespace std ; int sign..
[백준/C++] 25370번 카드 숫자 곱의 경우의 수 그냥 문제 하나 간단하게 풀고 싶어서 도전한 문제이다. 곱셈에 패턴이 보이지는 않고 1~9까지의 카드를 최대 7장 뽑는다면 매우 작은 숫자니 브루트포스 문제라고 생각하였다. 그러다 문득 곱셈이니 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1로 생각해보면 1~9를 곱한 것에 다시 1 ~ 9를 곱하는 형식을 N번 반복하는 형태가 되겠다는 생각을 하게 되었다. set을 이용해 중복 없이 key를 사용하면 편하겠다 생각했는데 sort가 되는 문제가 있어 배열 2개를 사용하여 중복 체크를 한 후 배열에 값들을 담아내는 형식으로 구현했다. (최대숫자도 400만 언저리니 배열 크기를 널널하게 잡았다.) /** * @file 25370.cpp * @author fpqpsxh * @date 2023-01-..
[백준/C++] 1920번 수 찾기 갑자기 동아리원 한 명이 이 문제 ios::sync_with_stdio(0) 하나 차이로 통과하고 못한다고 이야기해서 진짜인가? 하고 풀어봤다. 정답 비율을 보니 그럴 수 있겠다는 생각이 들었다. 문제를 보며 가장 먼저 한 생각은 그냥 10만개 솔트 N log(N) 2번이면 오바되고 하나의 배열을 솔트하고 이분탐색하는 방법이 시간 내에 통과할 수 있겠구나 했지만 귀찮아서 map으로 되나 짜봤다. /** * @file 1920 * @author fpqpsxh * @date 2023-01-10 */ #include using namespace std ; int main() { int N, M, tmp ; map mp ; vector ans ; cin >> N ; while(N--) { cin >> tmp ;..
[백준/C++] 25947번 선물할인 분명 실버2인데 생각보다 까다로웠던 것 같다. ICPC 2022 인터넷 예선 당시에는 1초라는 압박감에 pq를 사용해야하나 고민하다 뒤늦게 반례를 찾아서 생각해낸 방법은 Greedy(탐욕법)이었다. 작은 것부터 챙겨나가다가 못챙기는 순간이 생기면 그 물건을 할인해서 넣을 수 있는지 확인하고 그 이후 가지고 있는 값 중에 가장 큰 값을 차례대로 줄여가며 구매할 수 있는지 체크하면 되는 간단한 알고리즘이었는데 긴장해서 그런지 구현이 생각보다 막혔던 것으로 기억한다. 백준에 제출할 때는 로직은 분명 맞는데 왜 틀리지하고 고민하다가 마지막에 + 1을 해주게 되어 처음부터 넣을 수 없는 아이템일 때도 1로 체크되는 문제가 있었다. 역시 10% 이내나 90%이내에서 터지면 경계값 확인을 하는게 제일 좋은 것 같다...
[백준/C++] 25824번 빠른 오름차순 메시지 전달 그냥 주위 친구가 풀어낸 거 보고 나도 풀어볼까? 하고 문제를 풀게 되었다. 문제를 처음 봤을 때는 BFS / 다익스트라 or 플로이드와샬 이라고 생각했는데 BFS로만 풀릴 것 같았다. 다시 생각해보니 input이 12로 제한되어있고 이진트리로 가지치며 나오는 최종 경우의 수를 생각해봐도 leaf에서 2^6으로 모든 경우의 수가 128보다 적다. 3초나 주어지는 것을 보니 브루트포스로 풀어낼 수 있을 것 같았다. 풀며 식을 세우다가 느꼈는데 DP로 식을 세울 수 있어 보였다. 물론 dp식을 세우는데 실패해서 시간을 낭비하고 브루트포스로 구현하였지만 맞춘사람을 보니 BFS와 DP로 풀어낸 경우도 확인할 수 있었다. 브루트포스를 이진트리 느낌으로 구현하다보니 조금 귀찮아 골드 문제가 아니였나 싶다. #inc..
[백준/C++] 23306번 binary는 호남선 비오길래 구글에 binary호남선 쳤다가 이 문제까지 오게된 건 안비밀.. 인터렉티브를 처음 풀어봐서 난해했다. 인터렉티브는 출력문을 통해 입력을 받아올 수 있는 다소 신박한 문제였는데 인터렉티브 문제에서 팁을 주자면 표준 입력 버퍼를 비워주지 않으면 버퍼에 남아있는 쓰레기 값이 들어가게 된다. 이 문제에서는 매 입력마다 (여기서는 출력문을 통해 입력을 받으므로) 버퍼를 비워줘야 하니 endl 사용이 적합하다. 쉽다고 생각하고 무지성 제출했다가 틀려서 다시보니 질문을 log2(N)번 밖에 못하는 조건이 있었다. 곰곰히 생각해보니 문제에서 힌트를 모두 제공하고 있었다. 시작과 끝만 비교해서 올라간 횟수가 많은지 내려간 횟수가 많은지 확인할 수 있다.(00이나 11은 don't care이고) 0으로 시작해 ..

티스토리툴바