joseph0528 코딩 블로그

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 어느 한 위치를 선택했을 때 그 위치에서 최대로 갈 수 있는 개수를 저장하고 dfs를 돌면 된다. 최대 개수 구하는 방법은 한쪽으로 쭉 내려가고 더이상 내려갈 수 없을 때부터 +1씩 해주면 된다. import sys sys.setrecursionlimit(10**9) input=sys.stdin.readline a=int(input()) l=[list(map(int,..

solved.ac 티어 : 플래 3 www.acmicpc.net/problem/14288 14288번: 회사 문화 4 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 이 문제는 회사 문화 2, 회사 문화 3를3을 합친 문제인데 회사 문화 2를 저장하는 트리와 회사 문화 3을 저장하는 트리를 만들고 각각 업데이트를 해준 뒤 출력할 때 회사 문화 2의 출력 값+회사 문화 3의 출력 값을 해주면 된다. BOJ 14268(회사 문화 2)풀이 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번..

solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/14268 14268번: 회사 문화 2 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 회사 문화 1과 같은 문제인데 1은 마지막에 모든 정점마다 합을 구해주는 거고 2는 2가 들어올 때마다 구간의 합을 구해주는 것이다. BOJ 14267(회사 문화 1)풀이 solved.ac 티어 : 골드 4 www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가..

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net dfs으로 각 위치마다 구간을 새로 저장해준 뒤 입력으로 들어오는 값의 구간에다가 w를 더해주고 마지막에 1부터 n까지 i번째점의 구간 합을 출력해주면 된다. #include using namespace std; typedef long long ll; typedef pair nod; const ll N=1000000; ll n,m; vector graph[N]; nod Qu..

solved.ac 티어 : 플래 5 www.acmicpc.net/problem/14574 14574번: 헤븐스 키친 남규는 요즘 군입대를 기다리며 하루 종일 유튜브를 본다. 남규가 가장 좋아하는 채널은 ‘Heaven`s kichen’이다. 이 프로그램에서는 N명의 요리사가 매일 둘씩 요리 대결을 펼치고, 승리한 요리사 www.acmicpc.net 모든 간선을 이어주고 가중치는 로 해준다. 그리고 스패닝 트리를 만들어 준다음에 사용한 간선들을 저장해서 트리를 만든 다음 dfs으로 탐색을 하면서 밑에부터 위로 가면서 출력해주면 된다. import sys sys.setrecursionlimit(10**9) m=int(input()) e=[] def find(a): if uf[a]

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 이 문제는 각 섬들마다 다리를 이어서 모든 섬을 오갈 수 있게 하면서 다리의 길이가 최소가 되게 해야 된다. 이때 다리의 길이를 두 점의 가중치로 생각하면 최소 스패닝 트리가 된다. 이제 입력을 dfs으로 탐색해서 섬을 나누고 다리를 이은 다음 최소 스패닝 트리를 구해주면 된다. import sys sys.setrecursionlimit(10**9) a,..

solved.ac 티어 : 골드 2 S와 모든 K 간의 거리를 구해서 스패닝 트리를 구해주면 된다. import sys from collections import deque sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 골드 4 www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 아주 간단한 mst문제이다. 점의 y, x가 주어지고 정점 개수-1개의 간선을 이어야 되니 모든 점을 이어준다. 이때 가중치는 두 점의 거리가 된다. 그러므로 두 점의 x좌표의 차 제곱 + 두 점의 y좌표 차 제곱을 루트 해준 값이 두 점 사이의 거리가 된다. import sys,math sys.setrecursionlimit(10**9) def find(a): if uf[a]

solved.ac 티어 : 골드 3 www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 이문제는 기본 mst(최소 스패닝 트리)에서 간선을 추가할 때 두 점이 다른 점이라면 추가하는 방식으로 하면 된다. 그리고 마지막에 -1 처리를 해주면 된다. import sys sys.setrecursionlimit(10**9) def find(a): if uf[a]