문제풀이/백준
-
[백준]13904: 과제 - JAVA문제풀이/백준 2021. 8. 5. 21:02
[백준]13904: 과제 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 풀이 🪑 골드 문제 이길래 처음에 괜히 어렵게 생각해서 DP인가.. 했는데 그냥 구현문제였다. 📝 문제를 정리해 보자! 하루에 하나의 과제를 할 수 있다. 과제를 마무리 할 때마다 마무리한 과제의 점수를 얻는다. 🔧 문제를 풀어보자! 입력받은 과제들의 정보를 날짜 순서대로 내림차순 한다. 제일 마지막 날짜에서 부터 가능한 과제를 하나씩 우선순위 큐에 넣어준다. 우선순위 큐에서 가장 큰 점수를 갖는 과제를 하나씩 꺼내어 결과에 더해준다. 🙋♀️ 일단 예제를 함께 따라가 보자. 어떤 ..
-
[백준]13422: 도둑 - JAVA문제풀이/백준 2021. 8. 4. 14:28
[백준]13422: 도둑 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 풀이 🪑 문제가 장황하게 적혀있지만 한 줄로 정의할 수 있는 문제였다. 간단한 투포인터 문제이다. 📝 문제를 정리해 보자 N개의 집들 중에서 M개의 연속된 집을 선택하여 K이하의 돈을 훔칠 수 있는 경우의 수를 구하는 문제이다. 문제 구현에 대한 아이디어는 굉장히 쉽지만, 엣지 케이스가 있으니 유의해야 한다. 문제가 쉽다고 무턱대고 구현했다가 엣지 케이스에서 걸려버렸다 ㅠ 🔧 이제 풀어보자! 입력 받은 정보를 저장한다. 집들은 항상 연속된 M개를..
-
[백준]2637: 장난감 조립 - JAVA문제풀이/백준 2021. 8. 3. 14:55
[백준]2637: 장난감 조립 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 풀이 🪑 처음 문제를 읽을 때는 다익스트라나 플로이드 와샬인가 싶다가 부품별로 만들어 지는 순서가 중요하다는 조건을 보고 위상정렬이 떠올랐다! 📝 문제의 조건을 보자. 완제품 N을 만드는데 필요한 모든 기본 부품의 종류와 수를 구해야 한다. 각 정보는 X번 부품을 만드는데 Y부품 K개가 필요함을 의미한다. 주어지지 않은 정보는 기본 부품이 된다는 것을 알 수 있다. 🔧 문제를 풀어보자! 정보를 입력 받을 ..
-
[백준]22255: 🦖호석사우루스 - JAVA문제풀이/백준 2021. 7. 31. 15:51
[백준]22255: 호석사우루스 22255번: 호석사우루스 (1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (3, 3) -> (3, 4) -> (4, 4) -> (5, 4) -> (5, 5) 8번 만에 갈 수 있고 이게 최소이다. www.acmicpc.net 풀이 🪑 시작 노드에서 도착 노드로 가는 최소 비용을 구하는 문제이다. (최단 거리 아님!) 한 정점에서 다른 정점으로 가는 최소비용! 다익스트라 문제이다. 📝 문제의 조건을 정리해 보자!' 3K번째 이동: 상 하 좌 우로 이동 가능하다. 3K + 1번째 이동: 상 하로 이동 가능하다. 3K + 2번째 이동: 좌 우로 이동 가능하다. 시작노드 ~ 도착노드로 가는 최소 비용을 구한다. 🔧 문제 풀이 과정은 다음과 같다. 다익스트..
-
[백준]22254:👨🔧공정 컨설턴트 호석 - JAVA문제풀이/백준 2021. 7. 29. 13:57
[백준]22254: 공정 컨설턴트 호석 22254번: 공정 컨설턴트 호석 거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 $N$개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정 www.acmicpc.net 풀이 🪑 이전 문제가 너무 어려웠어서 잔뜩 쫄아있었는데 4번문제로 나왔던 이번 문제는 어렵지 않게 풀었다. 이분탐색 + 우선순위 큐(자료구조) 문제이다. 📝 문제의 조건을 살펴보자. 각 선물마다 제작에 필요한 시간이 정해져 있다. 1~K까지의 공정 라인에서 맞춤형 선물들을 제작하는데 소요되는 최소 라인의 수를 구한다. 🔧 문제를 풀어보자! 탐색 공정 개수를 기준값으로 이분탐색을 한다. mid개의 공정으로 맞춤형 선물..
-
[백준]22253: 👨🎨트리 디자이너 호석 - JAVA문제풀이/백준 2021. 7. 28. 22:56
[백준]22253: 트리 디자이너 호석 22253번: 트리 디자이너 호석 트리를 너무나 사랑하는 효성이는 트리 분재 전문가이다. 효성이가 기르는 모든 트리는 정점과 간선으로 이루어져 있다. 정점은 $1$번부터 $N$번 정점까지 존재하며, 간선은 서로 다른 두 정점을 www.acmicpc.net 풀이 🪑 정말 어려웠다... 이 문제 때문에 오늘 하루를 다 날려버렸따 ㅎㅎ,, 하지만 새로운 유형인 트리DP에 대해서 깊게 이해할 수 있었던 시간이었다..! 📝 문제의 조건! 루트는 항상 1번 노드이다. 정점에는 0~9까지의 숫자가 쓰여있다. 임의의 부모 노드에서 자식 노드 까지 가는 경로에서 선택하는 숫자가 오름차순이 되는 경우의 수를 구한다. 숫자의 오름차순이 되는 경우...LIS가 떠올랐다. 이전에 비슷한 ..
-
[백준]22252:🕵️♂️ 정보 상인 호석 - JAVA문제풀이/백준 2021. 7. 27. 15:45
[백준]22252: 정보 상인 호석 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 풀이 🪑 우선순위큐, 해쉬맵을 활용한 자료구조 문제이다. 📝 문제의 조건들을 정리해 보자. 가치 순으로 가장 비싼 정보들을 구매한다. 한번 거래한 정보는 파기된다. 1로 시작하는 쿼리는 정보를 얻은 고릴라와 가지고 있는 정보 가치를 의미한다. 2로 시작하는 쿼리는 거래할 고릴라와 구매하려는 정보의 개수를 의미한다. 정보는 시간 순서대로 주어진다. 🤔 처음에는 문제가 잘 이해가 되질 않아 예제를 보며 따라가 보았다. 예제를 ..
-
[백준]22251: 🤷♂️빌런 호석 - JAVA문제풀이/백준 2021. 7. 26. 13:56
[백준]22251: 빌런 호석 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 풀이 🪑 굉장히 재미있는 구현 문제였다. 📝 문제의 조건을 정리해 보자. 7개의 표시등으로 이루어진 디스플레이를 K개의 자리수로 표현한다. 디스플레이 표시등 중에 최소 1개, 최대 P개를 반전시킨다. (자기자신으로 반전하는 경우는 제외한다.) 반전 이후에도 올바른 수가 보여져야 하며 수는 1이상 N이하여야 한다. 반전시킬 표시등을 고를 수 있는 경우의 수를 계산한다. 🙋♀️ 문제 풀이 과정을 도출해 내는 과정을 다음과 같았다. - 처음에는 '백트랙킹'으로 반전시킬 표시등의 수를 골라 반전시켜서 수를 만들 수 있는지, ..