본문 바로가기

문제 해결/BOJ117

[백준] 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 트리 DP 문제입니다. 리프노드부터 탐색하면서 현재 노드가 얼리어답터인 경우와 그렇지 않은 경우 가질 수 있는 최소값을 DP 배열에 기억해놓으면 됩니다. 현재를 얼리어답터로 만드는 경우에는 자식 노드들이 얼리어답터여부에 상관없이 최소값만의 합을 구하고 현재를 얼리어답터로 만들지 않는 경우에는 무조건 자식들이 얼리어답터여야합니다. 이렇게 해서 루트 노드인 1가 얼리.. 2023. 3. 29.
[백준] 색종이 - 3 https://www.acmicpc.net/problem/2571 2571번: 색종이 - 3 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 색종이가 덮고 있는 영역이라면 넓이를 구하는 방식으로 풀이하였습니다. 시작점을 기준으로 x 좌표를 늘려가면서 해당 width를 기준으로 얻을 수 있는 최대 영역의 넓이를 구하는 방식으로 구하였습니다. height의는 현재까지 만난 길이중 가장 짧은 길이에 의해 결정이 되게 됩니다. import sys #sys.stdin = open("input.txt", "r") INT_MAX = sys.ma.. 2023. 3. 28.
[백준] 마피아 https://www.acmicpc.net/problem/1079 1079번: 마피아 첫째 줄에 참가자의 수 N이 주어진다. 둘째 줄에는 각 참가자의 유죄 지수가 주어진다. 셋째 줄부터 N개의 줄에는 배열 R이 주어진다. 마지막 줄에는 은진이의 참가자 번호가 주어진다. N은 16보다 www.acmicpc.net 완전 탐색 문제입니다. 단순하게 완전 탐색만 진행했을 때에는 시간 초과가 발생합니다. 1명이 남았고 그게 은진이인 경우에는 더이상 탐색이 무의미하므로 탐색을 중단하는 flag 코드가 없으면 시간초과가 발생하게 됩니다. 다만 pypy3로 풀이했을 때에는 메모리 초과가 발생하는데 이에 대해서도 알아봐야할 것 같습니다. import sys sys.setrecursionlimit(10 ** 8) # sy.. 2023. 3. 27.
[백준] 소형기관차 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net DP 문제입니다. 먼저, 각 인덱스를 시작으로 소형기관차가 연속적으로 태울 수 있는 손님의 수를 계산하여 저장한 다음 각 연속적으로 저장되어 있는 칸이 1 ~ 3번째에 해당하는 경우에 태울 수 있는 최대 손님의 수를 계산해주면 됩니다. import sys sys.stdin = open("input.txt","r") input = sys.stdin.readline n = int(input()).. 2023. 3. 26.
[백준] 음악프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상정렬을 활용하는 문제입니다. 모든 출연자에 대해 순서를 정해주어야하는데 각 작가별로 입력받은 순서에 따라 그래프를 구축한 다음 위상정렬을 통해 순서를 정해주면 됩니다. 순서를 정해줄 수 없는 경우는 위상정렬 시작을 위해 큐에 넣는 과정에서 큐에 하나의 노드도 넣을 수 없는 경우, 위상 정렬중에 in_node의 값이 음수가 되는 경우 그리고 위상정렬이 끝났는데 n개의 노드에 .. 2023. 3. 25.
[백준] 벡터 매칭 https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 한참의 고민 끝에 풀은 문제입니다. 벡터라는 말에 너무 쫄았던 것 같습니다. 벡터를 만들기 위해서 2가지를 선택하여 한쪽에서 나머지를 빼준 다음 만들어진 벡터의 합을 구하기 위해 x, y를 모두 합쳐야합니다. 예를 들어 (x1, y1), (x2, y2), (x3, y3), (x4 y4)가 있을 때 (x1 - x2, y1 - y2), (x3 - x4, y3 - y4) 2개의 벡터를 만들 수.. 2023. 3. 25.
[백준] 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 배낭문제를 활용하여 풀이할 수 있습니다. 무게 추들을 순회하면서 현재까지 잴 수 있는 무게에서 더하거나 빼면 잴 수 있는 무게가 되게 됩니다. 예를 들어, 1, 3, 5 무게 추가 있다고 가정하면 1을 순회할 때는 {1}만 가능하고 3을 순회할 때는 {1, 3, 3 - 1 , 1 + 3}이 가능하므로 {1, 2, 3, 4}가 가능해지고 5를 순회할 때에는 {1, 2, 3, 4, 5, 1 + 5, 2.. 2023. 3. 24.
[백준] 치즈 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net BFS를 활용한 문제입니다. 가장자리(0,0)부터 BFS를 통해 사방탐색을 진행하면서 다음이 빈 공간이면 큐에 넣어주고 치즈이면 공기와 맞닿아있는 치즈이므로 cnt를 늘려준 다음 2이상인 치즈는 제거해주면 됩니다. import sys from collections import deque sys.stdin = open("input.txt", "r") input = sys.stdin.re.. 2023. 3. 23.
[백준] 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드-와샬을 활용하면 풀이가 가능한 문제입니다. a b사이의 간선이 양방향인 경우에는 dist 배열에 dist[a][b], dist[b][a]를 0으로 만들어주고 a b사이의 간선이 양방향이 아닌 경우에는 dist[a][b]=0, dist[b][a]=1을 넣어주면 됩니다. 이렇게 해주면 단방향 간선으로 양방향으로 바꾸는 효과가 생기게 됩니다. 따라서 a-b사이의 간선을 양방향으로 바꾸었을 때.. 2023. 3. 22.

티스토리툴바