0m1n's Develog

문제 출처 : https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 풀이 고층 빌딩 리스트가 주어지는데, 가장 많은 빌딩이 보이는 수를 출력하는 문제이다. 이때 A에서 B빌딩이 보이려면 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 처음에 두 선분을 구하고 사이에 있는 빌딩의 높이가 그 선분을 건드리는지 확인해봐야하나 고민했지만, 결론은 기울기였다. 2중 for문을 돌며 모든 빌딩과 다른 빌딩을 확인해 해당..

문제 출처 : https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 풀이 맥주 한 박스(20개)를 들고 50m마다 맥주를 한병씩 마시는데, 편의점에 방문하면 맥주를 채울 수 있다. 집에서 페스티벌 좌표까지 이동할 수 있는지 묻는 문제이다. 직관적으로 풀면 해결되는 문제였다. 먼저 맥주 20개를 가지고 있으니 최대 1000m까지 이동할 수 있다. bfs로 풀면 이제 고려해야 할 경우는 2가지이다. 1. 1000m 맨해튼 거리 내 편의점이 있으면 ..

문제 출처 : https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 브루스포스로 해결하면 시간 초과가 발생한다. map을 이용해서 듣도 못한 사람을 저장하고, 보도 못한 사람을 해당 map에서 찾아 있는 경우 vector에 추가 해주었다. sort 함수를 사용해 사전순으로 출력하였다. (sort를 사용하려면 algorithm 헤더 파일을 선언해주어야 한다!) 이분탐색(binary_search)을 활용해 겹치는 사람을 찾는 방법도 있다. 아래 ..