김머성 블로그

[BAE/<JOON> 문제풀이] 1670. 정상회담 2

https://www.acmicpc.net/problem/1670 1670번: 정상 회담 2 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. www.acmicpc.net 핵심:: 카탈란 수열 문제 풀이:: 카탈란 수열 의견:: 골드 3임 이게 ( 저울 문제랑 같은 난이도 2. ??? ) 코드:: 더보기 #include #include #include using namespace std; using ull = unsigned long long; ull dp[5002]; int main() { dp[1] = 1; dp[2] = 1; for (int i = 3; i > n; n /= 2; cout

[BAE/<JOON> 문제풀이] 2437. 저울

핵심:: 물건의 무게 순으로 정렬했을 때 sum(arr[0] ~ arr[i - 1]) + 1 >= arr[i] 를 만족한다면 그 사이의 무게 값들은 모두 만들 수 있다. 풀이:: 풀이 보고 품 문제 보자마자 숫자판 마술이 생각나긴 했는데 증명을 못하니까 해결이 힘들었다. 핵심 과정 증명은 다음과 같다. 명제 : 물건 n개가 있으며 무게 순으로 정렬한 모든 물건에 대해 sum(arr[0] ~ arr[i - 1]) + 1 >= arr[i] 가 만족함. 현재 사용 가능한 모든 숫자의 합보다 큰 수를 만들기 위해서는 무조건 새로운 수가 필요하다. 우리는 모든 양의 정수를 만들어야하므로 합 k까지의 모든 정수를 만들었다면 다음으로 필요한 새로운 수는 반드시 k + 1 이 될 것이다. 그 이상의 수 p 가 주어진 ..

[BAE/<JOON> 문제풀이] 1504. 특정한 최단 경로

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 핵심:: Dijkstra 기본 문제 풀이:: 각각의 경유지를 c1, c2 라고 할때 s -> c1 -> c2 -> e의 거리와 s -> c2 -> c1 -> e 의 거리 중 더 짧은 것을 출력한다. 의견:: 다익스트라 코드 잘못짰다가 틀렸습니다 18연속 매드무비 찍고 겨우 고침 코드:: 더보기 #include #include #include #inclu..

[BAE/<JOON> 문제풀이] 1504. 특정한 최단 경로

https://www.acmicpc.net/problem/1081 1081번: 합 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오. www.acmicpc.net 핵심:: 책페이지와 동일한 숫자 갯수 카운팅 알고리즘 사용 풀이:: 책페이지 알고리즘을 사용해 각자리 숫자의 출현 횟수를 구하고 각 숫자를 곱해 합을 구한다. L부터 U까지의 합이 필요하므로 S(U) - S(L - 1)를 구하면 된다. 의견:: 책페이지랑 사실상 같은 문젠데 왜 이게 1티어 더 낮은지 모르겠음 코드:: 더보기 #include #include #include #include using namespace std; using ull = long long; struct bk { int f..

[BAE/<JOON> 문제풀이] 1081. 합

https://www.acmicpc.net/problem/1081 1081번: 합 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 프로그램을 작성하시오. www.acmicpc.net 핵심:: 책페이지와 동일한 숫자 갯수 카운팅 알고리즘 사용 풀이:: 책페이지 알고리즘을 사용해 각자리 숫자의 출현 횟수를 구하고 각 숫자를 곱해 합을 구한다. L부터 U까지의 합이 필요하므로 S(U) - S(L - 1)를 구하면 된다. 의견:: 책페이지랑 사실상 같은 문젠데 왜 이게 1티어 더 낮은지 모르겠음 코드:: 더보기 #include #include #include #include using namespace std; using ull = long long; struct bk { int f..

[BAE/<JOON> 문제풀이] 2150. Strongly Connected Component

https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 핵심:: 코사라주 알고리즘 / 타잔 알고리즘 중 코사라주 알고리즘 풀이 SCC란:: 강한 연결 방향 그래프 연결 그래프에 존재하는 부분 집합 Z에 속하는 모든 무작위 정점 (A, B)에 대해 A -> B로의 연결이 가능하다면 Z를 SCC라고 한다. 또한 SCC를 구분할 때에는 가장 큰 SCC만 찾도록 한다. 따라서 하나의 그..