본문 바로가기

전체 글23

백준 15686번 | 치킨 배달 (C++ 풀이) 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 사용 알고리즘 : 완전 탐색 + 백트래킹 삼성 SW역량테스트 문제였네요. 저는 일단 완전탐색 + 백트래킹 + 약간의 그리디한 생각으로 풀었습니다. ​ 먼저 문제 해석을 잘 해야 합니다. 주어진 치킨집 중에서 최대 M개를 선택하고, 도시의 치킨 거리의 최소를 구하라고 합니다. 여기서 생각해볼만 한 것은, 치킨집을 최대 M개 선택하라 하였으니, 1개부터 M개까지 고를 .. 2022. 10. 1.
백준 1939번 | 중량제한 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 사용 알고리즘 : 그래프 탐색(BFS) + 파라메트릭 서치 시간 복잡도 : O((N + M) * log(max(K))) 그래프 탐색 + 파라메트릭 서치를 이용하여 풀었습니다. ​ 먼저 Naive한 풀이를 생각해 봅시다. 섬과 다리의 정보를 받아서 양방향 그래프화 시킵니다. 그 후 옮길 물품들의 중량을 k라고 했을 때, 섬 A에서.. 2022. 10. 1.
백준 14890번 | 경사로 (C++ 풀이) 문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 사용 알고리즘 : 구현 꽤 까다로운 구현 문제였습니다. ​ 저는 일단 입력을 받고 나서 데이터를 순서쌍 (칸의 높이, 같은 높이의 칸이 연속해서 인접해있는 개수) 로 바꿔서 처리했습니다. 예를 들어 3, 2, 2, 1, 2, 3 이 입력으로 들어온다면 (3,1), (2,2), (1,1), (2,1), (3,1) 로 바꾸는 식입니다. ​ 이제 경우를 나눠서 봐보죠. 편의를 위해 저 위의 순서쌍을 (A[i].fi.. 2022. 10. 1.

티스토리툴바