boj, 백준) 12784. 인하니카 공화국 (C/C++)
1. 문제 링크 https://www.acmicpc.net/problem/12784 12784번: 인하니카 공화국 인하니카 공화국은 1번~ N번까지 N개의 섬으로 이루어진 나라이다. 이 나라에서는 섬 간의 왕래가 매우 어려웠지만, 위대한 다리 설계자 ‘진’이 두 섬을 연결하는 다리를 최소한의 개수로 만들 www.acmicpc.net 2. 문제 개요 인하니카 공화국은 1번 ~ N번까지 N개의 섬으로 이루어진 나라이다. 두 섬을 연결하는 다리를 최소한의 개수로 만들어 모든 섬 간의 왕래가 가능하도록 만들었다. 1번 섬을 제외한 다리가 하나밖에 없는 어느 섬에서 유명한 연쇄 살인마 괴도 루팡이 자신의 목숨을 노리고 있다. 몇 개의 다리를 폭파하여, 루팡이 있을 가능성이 있는 모든 섬에서 자신의 섬으로의 모든 ..
boj, 백준) 17404. RGB거리 2 (C/C++)
1. 문제 링크 www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 문제 개요 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규직을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성. 1번 집의 색은 2번, N번 집의 색과 같지..
boj, 백준) 1086. 박성원 ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 2. 문제 개요 서로 다른 정수로 이루어진 집합이 있다. 이 집합의 순열을 합치면 큰 정수 하나를 만들 수 있다. 합친 수가 정수 K로 나누어 떨어지는 순열을 구하는 프로그램을 작성하시오. 박성원이 우연히 정답을 맞출 확률을 분수로 출력하는 프로그램을 작성하시오. 3. 문제 힌트 (1) 숫자의 길이가 최대 50 - 입력을 string으로 받아서 나머지를 계산해야 함. 손으로 직접 나머지를 구하는 방법 그대로 적용하자. -> O(L), ..
boj, 백준) 9177. 단어 섞기 (C / C++)
1. 문제 링크 www.acmicpc.net/problem/9177 9177번: 단어 섞기 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 www.acmicpc.net 2. 문제 개요 세 개의 단어가 주어졌을 때, 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 계산하는 프로그램을 만들어보자. 3. 문제 힌트 완전탐색을 하면 어떻게 될까..? aaab aaac aaabaaac이 입력으로 주어지고, 세 번째 단어인 aaabaaac의 왼쪽 끝에서 오른쪽 끝으로 탐색을 한다고 해보자. 첫 번째 a는 "aaab"의 a인지, "aaac"의 a인지 알..
boj, 백준) 2670. 연속부분최대곱 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된 www.acmicpc.net 2. 문제 개요 N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아 그 곱을 출력하는 프로그램을 작성하시오. 3. 문제 힌트 우선 모두 자기 자신만 곱한 걸 나타내기 위해 초기화는 자기 자신들로 해주자. 곱해 나갈 때, 곱한 결과가 자기 자신보다 크다면 누적하는 그런 형태로 나타내 주자. 음수가 없기 때문에 문제는 없다. 코드를 보는 편이 ..
boj, 백준) 1949. 우수 마을 ( C / C++)
1. 문제 링크 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, �� www.acmicpc.net 2. 문제 개요 N개의 마을로 이루어진 나라가 있다. 1부터 N까지 번호가 붙어있다고 하자. 이 나라는 Tree구조로 이루어져 있다. 마을과 마을 사이를 잇는 N-1개의 길이 있으며 양방향 간선이다. (1) '우수 마을'로 선정된 마을 주민 수의 총합을 최대로 해야 한다. (2) 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우..