완전탐색4 백준 - 도도의 음식 준비 - 22953 - swift https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net 문제는 완전탐색과 이분탐색으로 볼 수 있다. 완전탐색에는 순열과 조합을 이용했다. 크게 문제는 최적의 시간을 찾는 것으로, 각 요리사들에는 요리 시간이 정해져있고, K개의 음식을 모두 준비하는데 걸리는 가장 빠른 시간을 찾는 문제다. 이러한 유형은 미리 최적의 시간이 X라고 정하고서 탐색하는 방법, 즉 이.. 2021. 9. 1. 백준 - 빌런 호석 - 22251 - swift https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 문제 유형은 구현, 완전탐색 또는 비트마스킹이 될 수 있다. 하나의 문제에서 다양한 접근법이 가능하므로 정말 좋은 문제인 것 같다. 어떻게 이런 문제를 만드는지 정말 대단하다. 내 기준에서는 조금 난이도가 있었다 내 접근법 우선 처음 접근법( 구현 + 완전탐색 ) 은 다음과 같았다. 하나의 디스플레이에 0부터 9까지 숫자를 표현할 수 있고, 각 숫자마다 필요한 LED가 다르다. 또, 각 디스플레이마다 LED는 최대 7개이다. 호석이는 1부터 최대 P개까지 LED를 반전시킬 수 있다... 2021. 8. 27. 백준 - 주간 달력 - 22936 - swift https://www.acmicpc.net/problem/22936 22936번: 주간 달력 주간 달력(주력)은 일요일부터 토요일까지 총 7일간의 일정이 들어있는 달력이다. 작년 수현이는 일 년 짜리 달력에 코팅 용지를 붙여 사용했는데, 올해는 조금 더 똑똑해져서 주력에 테이프를 www.acmicpc.net 완전 탐색 및 누적합 문제 유형 같다. ( 알고리즘 유형에는 구간합이 없었지만, 내가 난이도 기여해서 누적합을 추가했다 ) 나름 재밌었던 문제다! 문제의 지문이 조금 애매한 것 같은데.. ( 그래도 풀 수 있었으니 ) 우선 핵심 지문들이 있다. 주력 하나에 들어갈 수 있는 일정의 개수는 제한이 없고, N개의 주력은 서로 연속되어야 한다. 주력의 맨 처음 날짜는 1 이상이어야 하고, 요일은 신경 쓰지 .. 2021. 8. 22. 백준 - 쿠키크루 - 22939 - swift https://www.acmicpc.net/problem/22939 22939번: 쿠키크루 밀가루반죽으로 잘 구워진 킴쿠키는 광활하고 평평한 들판 위에 세워진 쿠키나라의 시민이다. 킴쿠키는 케이크나라의 침략으로 어려워진 쿠키나라를 지키기 위해 할 수 있는 일이 없을까 늘 고 www.acmicpc.net 완전탐색 및 구현 문제라고 볼 수 있다. 처음에 가장 가까운 토핑들만 탐색하는 bfs로 접근했는데 틀렸다. 사실 그 방법으로도 의문점이 있었다. 반례가 존재할 것 같았다. 집 - [토핑 1, 2, 3] - 도착지점 이렇게 bfs로 탐색한다고 해서 최소거리가 보장 된다는 점이 없다는 것이다. 그래서 이 점을 해결하기 위해 순열로 각 토핑들의 방문위치를 정해주는 것이다. 총 3개의 토핑들이 있으므로, 총 6개.. 2021. 8. 22. 이전 1 다음
