본문 바로가기

백준 문제 풀이

 (152)
백준 20208번 진우의 민트초코우유 (C++) https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 이전에 풀어본 문제들을 다시 풀어보는 프로젝트(?)를 진행중이다. 문제 양치기보다 각 문제들을 더 잘 파악하는게 좋을 것 같다는 생각이 들었다. 모든 문제를 내 힘으로 푼 것도 아니기 때문이다. 1. 문제 조건 - 가능한 많은 초코우유를 마시고 돌아올 수 있는 최대 민트초코우유 개수를 찾아낸다. 2. 접근법 - 먼저 보고 생각나는 건 DFS 완전탐색이다. 그리고 이것은 틀린 생..
백준 2533번 사회방 서비스(SNS) C++ https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 트리에서 다이나믹 프로그래밍 문제이다. 진짜 너무 어렵다 이런거 어떻게 풀어야하는 걸까. 계속 하면 할 수 있겠지라 생각하며 계속 하는 수 밖에 없다. * 트리에서 다이나믹 프로그래밍을 적용할 때는 보통 이번 노드에서의 dp값 다음 노드까지 포함했을 때 dp값으로 이어지는 top Down방식이거나 leaf까지 도달한 후 올라오며 값을 갱신하는 Bottom Up 방..
백준 1092번 배( C++) https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 정렬, 그리디 알고리즘 문제이다. 난 그리디 알고리즘이 약한 것 같다. - 내 접근법 먼저 Crain과 Weight는 최대한 비슷한 값 끼리 매져주는 것이 좋다. 그러므로 난 Crain은 오름차순, Weight는 내림차순 정렬을 해주었다. 그리고 Crain의 시작부분과 Weight의 시작부분부터 비교하며 크레인에 적재가 가능하면 Weight 벡터에서 삭제하고 다음 크레인의 상태로 ..
백준 25634번 - 전구 상태 뒤집기 (C++) https://www.acmicpc.net/problem/25634 25634번: 전구 상태 뒤집기 $N$개의 전구가 일렬로 세워져 있다. 전구는 켜져 있을 수도 있고 꺼져 있을 수도 있다. 만약 $i$번째 전구가 켜져 있다면 그 전구의 밝기는 $a_i$이다. 연우는 $N$개의 전구 중 연속한 전구를 한 개 www.acmicpc.net 문제 조건 - 한 시퀀스가 모두 바뀌었을 때를 가정한다. 길이가 3이면 1,2,3,1~2, 3~4, 1~3 이렇게 모든 전구를 바꾸어야한다. 반드시 단 1번은 바꾸어야한다. 내 접근 - dp로풀어야한다. 그리고 누적합으로 구하는 것인데 어떻게 하는지 모르겠어서 일단 dp로 생각해보기로 했다. 그러나 dp[index] = index까지의 최적합 으로 구하기에는 따져야할 것이..
백준 14226번 - 이모티콘 (C++) https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제조건 - 이모티콘의 개수를 늘리는 방법은 오직 붙여넣기 뿐이다. 화면의 이모티콘은 임의로 늘릴 수 없으나 삭제는 가능하다. 그리고 각 행동은 1초의 작업시간을 가진다. 내 접근 - 당연히 BFS 문제라고 생각했다. 최소,최단거리 문제이고 할 수 있는 행동이 3가지이다. 그러므로 BFS문제라 생각하는 것이 타당하다. 그러나 문제는 방문처리이다. 한 번 갔던 이모티콘 개수라 해도 담고있는 클립보드의..
백준 14658번 - 하늘에서 별똥별이 빗발친다. (C++) https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제조건 - 별똥별의 좌표가 주어지고 천을 펼쳤을 때 최대한 좌표가 천에 포함되어야한다. 내 접근 - 일단 N,M이 50만이라 절~~~대 O(N * M)으로는 풀어낼 수 없다. 그런데 아무리 봐도 문제가 브루트포스가 아니면 풀수가 없다고 생각됐다. 그래서 일단 풀 수 있는대로 해보니 당연히 시간초과가 났다. 어떻게 풀어야..
백준 14267번 회사 문화1 (C++) https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제조건 - 각 노드들은 부하를 자식으로 갖는다. 그리고 각 노드가 칭찬을 받으면 부하에게 전달되는 식으로 코드를 전개하면 된다. 내 접근 - 그래서 한 직원이 칭찬을 받으면 내리칭찬으로 dfs를 하고 칭찬을 받으면 dfs하는 식으로 구성했다. 그러나 이것은 dfs를 계속 반복하게 되어 좋지 않은 풀이가 된다. 그래서 시간초과에 걸렸다. 올바른 접근법 - 올바른 접근법은 칭찬을 받고 이전의 정보..
백준 2933번 - 미네랄 (C++) https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 나의 첫 골드 1 해금 문제이다. 문제 이해는 어렵지 않은데 구현하기가 매우 까다롭다. 그리고 DFS와 BFS의 깊은 차이를 느낄 수 있었다. - 문제 조건 두명이 번갈아가면서 미네랄을 하나씩 지우고 만약 하늘에 떠 있다면 미네랄이 클러스터 체로 떨어지게 된다. 그리고 미네랄이나 땅에 만날 때 까지 무너지며 클러스터의 형태는 변하지 않는다. - 나의 접근법 먼저 땅바닥에 붙어있는 미네랄들을 dfs한다. 그리고 ..

티스토리툴바