joseph0528 코딩 블로그

이 문제를 요약하면 N개의 수를 나열하고, 연속된 수들로 모둠을 여러 개 만든다. (1개에서 N까지 다양하게) 그때, 각 모둠끼리는 모두 직접 연결되어 있어야 하는데 그렇지 않을 경우, 부족한 개수만큼 점수가 오른다. 또 자신의 모둠이 아닌 다른 모둠과 연결되어 있을 때에도 개수만큼 점수가 오른다. 이때 점수의 최솟값을 찾는 문제이다. 이 그림으로 예를 들면, 이 그림에는 모둠이 2개가 존재하는데, 왼쪽에 있는 모둠은 내부에서 부족한 간선의 수는 3개가 되고, 오른쪽에 있는 모둠은 1개, 두 모둠을 잇는 간선 1개로, 이 그림은 5점을 가진다. 이 문제의 N의 범위는 2000 이하 이기 때문에 완전탐색은 통하지 않는다. 그럼 어떻게 풀 수 있을까? 누적 합과 dp 를 사용하면 풀 수 있다. dp [i]를..

문제를 요약하면 기존 입력에 N-M+1 개의 가중치가 L 인 간선을 추가로 만들어 모든 점끼리 갈 수 있게 할 때 두 빌라봉을 오가는데 드는 비용 중 가장 큰 값이 가장 작도록 N-M+1 개의 간선을 만드는 것이다. 즉 그래프가 1개 이상이라는 것인데 이때 각 그래프에서 점 하나를 골랐을 때 그 점과 한 그래프의 나머지 점들끼리의 거리의 최댓값이 가장 작은 점을 고른 뒤 한 그래프를 한 점이라고 했을 때 점들을 연결했을 때 점들 간의 거리의 최댓값이 가장 작아야 되기 때문에 점이라고 정의한 그래프의 값 중 가장 큰 값을 중앙에 두고 중앙을 중심으로 다른 점들이 중앙 점과 연결을 할 때 가장 작은 값을 찾을 수 있다. 맨 처음 그래프 내에서 거리의 최댓값이 가장 작은 값을 고르는 방법은 이전에 설명했던 사..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net dfs를 사용해서 거꾸로 탐색하는 방법을 사용했다. 문제를 보면 자신에게 오는 간선이랑 연결되어있는 점까지의 delay가 가장 큰 값을 골라야 된다. 그러므로 마지막부터 거꾸로 탐색하면서 max값을 저장한 뒤 현재 노드의 값을 더해서 출력해주면 된다. 문제에 있는 그림으로 예시를 들면 4번 노드에서 2,3번 노드로 탐색을 하고 2,3번 노드에서 1번노드로 탐색을 한다. 1번 노드에서는 갈 수..

https://www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 이 문제는 전에 올렸던 사무실 이전과 같은 방식의 문제이다. https://joseph0528.tistory.com/77 BOJ 16121(사무실 이전)풀이 https://www.acmicpc.net/problem/16121 16121번: 사무실 이전 첫 번째 줄에 모든 사무실 후보에 대한 모든 직원의 출근 경로 길이의 제곱을 모두 합한 값을 998,244,353으로 나눈 나..

https://www.acmicpc.net/problem/16121 16121번: 사무실 이전 첫 번째 줄에 모든 사무실 후보에 대한 모든 직원의 출근 경로 길이의 제곱을 모두 합한 값을 998,244,353으로 나눈 나머지를 출력한다. www.acmicpc.net 티어에 비해? 간단했지만 구현 때문에 말아먹은 문제이다. 인접한 두 점의 거리는 모두 1이기 때문에 제곱수의 규칙을 알면 쉽게 할 수 있다. 1부터 5까지만 표시해보자면 1^2=1,2^2=4,3^2=9,4^2=16,5^2=25 나열하면 1 4 9 16 25 이렇게 나오는 걸 알 수 있다. 여기서 규칙을 찾아보면 3,5,7,9 씩 커진다. 즉 전에 커진 수+2만큼을 전수에 더하면 (n+1)^2를 구할 수 있는 것이다. 그렇기 때문에 전 노드에서..

https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 처음에 봤을 땐 그리디로 큰 값부터 작은 위치에 값을 더하는 방식으로 하고 싶지만 그러면 틀리게 된다. 이 문제는 dp 문제인데 i번째 블록을 움직일 수 있는 경우는 왼쪽 탑에 올린다, 오른쪽 탑에 올린다, 버린다 이렇게 3가지의 경우가 있다. 이때 왼쪽 탑과 오른쪽 탑으로 분리하지 말고 왼쪽 탑과 오른쪽 탑과의 높이 차로 dp 테이블을 만들 수 있다. 그럼 이렇게 정의하자 dp ..

solved.ac 티어 : 플5 https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 이문제는 dp 문제있은데 dp인걸 알기 어렵다고 한다 이 문제는 빨강 페인트 a와 파랑 페인트 b 이렇게 두 개가 입력으로 들어오면 이 두 개의 양을 넘지 않는 선에서 만들 수 있는 모든 착륙장의 경우의 수를 출력하는 문제이다. k개의 동심원인 착륙장을 만든다고 했을 때 k번째 동심원을 파랑 페인트를 칠한다고 하면 파랑 페인트는 b-k가 되고 남은 k-1개의 동심원은 a와 b..

solved.ac 티어 : 골 5 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp로 된다는걸 알면 쉬운데 dp인걸 알아채기가 어렵다고 해서 골 5라고 한다. 바로 문제풀이를 설명하자면 dp [i][j]=(i, j) 번째 점을 포함하는 정사각형의 한 변의 최대 길이 이게 끝이다. dp [i][j]를 구하려면 (i, j) 번째 점이 0일 때는 0이고 1일 때는 (i-1, j)==(i, j-1)==(i-1, j-1) 이면 셋 중 하나의 값+1이 dp [i][j]가 되고 아닐 떼 셋 중 가장 작은값+1을 해주면 된다..

solved.ac 티어 : 골드 3 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 이 문제의 풀이는 생각보다 간단하다. 1에서부터 시작해서 dfs으로 끝점(괴도 루팡이 있다는 곳)까지 탐색하면서 지나온 길의 가중 치중 가장 작은 값을 찾고 모아지는 부분에서 더해주면 된다. 문제에 있는 예시로 설명을 해보겠다 괴도 루팡이 있을 수 있는 곳은 3,4,6,7번 점이다. 1부터 3,4,6,7인곳으로 dfs으로 탐색하면 된다. 일단 3부터 시작하..

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,..