Algorithm/Baekjoon117 1027. 고층 건물 (Python) 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 풀이 모든 건물에 대하여 왼쪽과 오른쪽으로 볼 수 있는 건물의 수를 카운트하여 가장 많이 보이는 빌딩의 수를 구하면 된다. 기울기(y의 증가량 / x의 증가량)를 이용하여 구할 수 있는데, 이때 왼쪽의 경우는 기울기가 작아져야 볼 수 있는 건물이고 오른쪽의 경우는 기울기가 커져야 볼 수 있는 건물에 해당한다. 위의 예제에서 높이가 7인 건물로 예를 들어보자. 왼쪽에 가장 먼저 건물 2가 있다. 두 건물의 지붕을 잇는 선분의 기울기는 5 (7-2 / 3-2)에 해.. 2022. 4. 12. 1167. 트리의 지름 (Python) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리의 지름을 구하려면 임의의 노드에서 가장 멀리 있는 노드 u를 구한다. 그 후 다시 노드 u에서 가장 멀리 있는 노드 v를 구한다. 이렇게 구한 노드 u와 노드 v의 길이가 트리의 지름이 된다. 이에 대한 증명은 링크를 참고하자... 코드 from collections import deque import sys input = sys.stdin.readline # node에서 가장 멀리 떨어져 있는 노드를 구하기 위한 bfs 함수 def .. 2022. 4. 11. 1005. ACM Craft (Python) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 건물을 짓는 것에 순서가 존재한다. 즉, 방향성이 존재하는 그래프 형태로 표시할 수 있고 그래프에 사이클이 존재하지 않기 때문에 위상정렬을 이용하여 문제를 해결할 수 있다. 각 건물을 지으며 다음으로 지을 수 있는 건물의 진입 차수를 하나씩 낮추면서 다음 건물의 걸리는 시간을 업데이트 해주면 된다. 이 때, 업데이트 되는 시간은 가장 오래 걸리는 시간으로 해주어야 한다. 예를 들어 문제의 예제를 살펴 보자. 일단 처음에 1번 건물을 지으며 10초가 걸.. 2022. 4. 11. 2632. 피자판매 (Python) 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 풀이 두 피자별로 구할 수 있는 부분 집합의 피자 조각들의 크기의 합을 구한다. 딕셔너리에 크기의 합별로 구할 수 있는 경우의 수를 카운트해준다. 고객이 원하는 피자의 크기를 target이라고 했을 때, A 피자에서 i (0 2022. 4. 11. 10836. 여왕벌 (Python) 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 www.acmicpc.net 풀이 입력으로 주어진 M(가로, 세로의 크기)에 맞춰서 M * M 사이즈의 배열을 만들어줄 필요는 없다. 제일 왼쪽 열과 제일 위쪽 행 크기만큼, 즉 2M - 1 크기만큼의 배열을 만들어서 애벌레의 크기를 기록해주면 된다. 그 이유는 다음과 같은 조건 때문이다. 제일 왼쪽 열과, 제일 위쪽 행의 애벌레들은 자신이 자라는 정도를 스스로 결정한다. 이들은 입력으로 주어질 것이다. 애벌레들이 자라는 정도를 왼쪽 제일 아래 칸에서 시작하여 위쪽으.. 2022. 4. 9. 10800. 컬러볼 (Python) 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이 두 개의 정보에 대해서 저장하는 리스트를 만들어둔다. 하나는 색깔 별 무게를 담아두는 리스트이고 다른 하나는 같은 사이즈를 가진 공들의 정보를 담아놓는 리스트이다. 입력받은 공들에 대해서 사이즈 기준 오름차순으로 정렬한다. 그 후 차례대로 공들의 무게를 누적하여 더해나간다. 모든 공들의 무게를 더한 값에서 현재 공과 같은 색을 가진 공들의 무게를 빼주면 현재 공이 잡을 수 있는 공들의 크기의 합을 구할 수 있다. 같은 사이즈의 경.. 2022. 4. 8. 이전 1 ··· 9 10 11 12 13 14 15 ··· 20 다음
