김머성 블로그

[BAE/<JOON> 문제풀이] 1162. 도로 포장

https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 핵심:: Dijkstra 문제에 고려해야 하는 요소 k가 추가 되었으므로 거리 배열에 한 차원 추가하고 DP 풀이:: 추가적으로 포장할 수 있는 횟수가 남아있다면 포장한 도로와 포장하지 않은 도로를 모두 우선순위 큐에 삽입한다. 또한 기존의 거리 배열에 남은 포장횟수를 고려하여 다음과 같이 변경한다. distance[k][목적지] = 목적지까지 k번 도로 포장 ..

[BAE/<JOON> 문제풀이] 1707. 이분 그래프

핵심:: 이분 그래프 개념 문제 풀이:: DFS를 수행하며 탐색되는 정점들에 1, 0을 번갈아 표시한다. 수행이 완료 되기 전에 표시해야할 번호와 정점에 이미 쓰여있는 번호가 겹친다면 이분 그래프가 아니다. 의견:: 코드:: 더보기 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int main() { int tc; cin >> tc; while (tc--) { int n, m; cin >> n >> m; vector arr(n + 1); for (int i = 1; i

[BAE/<JOON> 문제풀이] 11505. 구간 곱 구하기

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 핵심:: 세그 트리에서 Update 함수 부분 수정 풀이:: 합이나 최소값을 구하는 문제와 다른 점은 Update를 할 때 Bottom-Up 방식으로 해야한다. 합이나 최소값 비교는 순서와 상관 없이 부모 노드만 있어도 쉽게 역연산 ( 더하기 )을 수행할 수 있지만 곱셈의 경우에는 나누고 다시 곱하는 역연산이 필요한데, 값이 매우 크므..

[BAE/<JOON> 문제풀이] 11505. 구간 곱 구하기

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 핵심:: 세그 트리에서 Update 함수 부분 수정 풀이:: 합이나 최소값을 구하는 문제와 다른 점은 Update를 할 때 Bottom-Up 방식으로 해야한다. 합이나 최소값 비교는 순서와 상관 없이 부모 노드만 있어도 쉽게 역연산 ( 더하기 )을 수행할 수 있지만 곱셈의 경우에는 나누고 다시 곱하는 역연산이 필요한데, 값이 매우 크므..

[BAE/<JOON> 문제풀이] 14945. 불장난

https://www.acmicpc.net/problem/14945 14945번: 불장난 랩실의 크기가 3일 경우 (기웅, 민수)가 이동 가능한 방법은 (아래-아래, 대각-아래), (아래-아래, 대각-대각), (아래-대각, 대각-대각), (대각-아래, 아래-아래), (대각-대각, 아래-아래), (대각-대각, www.acmicpc.net 핵심:: DP가 아니라 초반 답 보고 규칙을 찾으면 된다. 풀이:: 초반 답을 나열 해보면 이항 계수가 나온다. 의견:: 2명이 갈 수 있는 위치 DP로 추적해야하는 문제인줄 알고 삽질했는데 진짜 끝이 없다. 꿀문젠줄 알고 풀었는데 10시 넘어서 품.. 코드:: 더보기 #include #include using namespace std; int main() { int n;..

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

https://www.acmicpc.net/problem/1132 1132번: 합 N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로 www.acmicpc.net 핵심:: 그리디긴 한데 구현에 더 가까운 문제같다. 풀이:: 우선 알파벳들이 각각의 자리에서 몇번씩 나오는지 계산하고 그 값을 숫자로 치환한다. 10의 자리에서 한번 출현, 1의 자리에서 12번 출현 -> 22 로 치환 해당 값들을 크기 순으로 내림차순 정렬하고 높은 값부터 큰 숫자를 주고 값을 계산하면 된다. 의견:: 그리디같은 구석이 없어서 풀 만한 문제 코드:: 더보기 #include #inclu..