CodeDrive

문제:

근우는 오늘 재미있는 카드 게임을 배우고 있다. 카드는 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있고, 색깔별로 1부터 9까지 숫자가 쓰여진 카드가 9장씩 있다. 카드는 모두 36(=4x9)장이다. 근우가 배운 카드 게임은 36장의 카드에서 5장을 뽑고, 아래와 같은 규칙으로 정수를 계산하는 것이다.

각 카드는 다음과 같이 나타낸다. 카드의 색깔은 영어 대문자 R, B, Y, G로 나타내는데, R은 빨간색, B는 파란색, Y는 노란색, G는 녹색을 뜻한다. 예를 들어서 Y8은 노란색 8을 나타내고, B5는 파란색 5를 나타낸다.

<점수를 정하는 규칙>

1. 카드 5장이 모두 같은 색이면서 숫자가 연속적일 때, 점수는 가장 높은 숫자에 900을 더한다. 예를 들어, 카드가 Y4, Y3, Y2, Y5, Y6 일 때 점수는 906(=6+900)점이다.
2. 카드 5장 중 4장의 숫자가 같을 때 점수는 같은 숫자에 800을 더한다. 예를 들어, 카드가 B3, R3, B7, Y3, G3 일 때 점수는 803(=3+800)점이다.
3. 카드 5장 중 3장의 숫자가 같고 나머지 2장도 숫자가 같을 때 점수는 3장이 같은 숫자에 10을 곱하고 2장이 같은 숫자를 더한 다음 700을 더한다. 예를 들어, 카드가 R5, Y5, G7, B5, Y7 일 때 점수는 757(=5x10+7+700)점이다.
4. 5장의 카드 색깔이 모두 같을 때 점수는 가장 높은 숫자에 600을 더한다. 예를 들어, 카드가 Y3, Y4, Y8, Y6, Y7 일 때 점수는 608(=8+600)점이다.
5. 카드 5장의 숫자가 연속적일 때 점수는 가장 높은 숫자에 500을 더한다. 예를 들어 R7, R8, G9, Y6, B5 일 때 점수는 509(=9+500)점이다.
6. 카드 5장 중 3장의 숫자가 같을 때 점수는 같은 숫자에 400을 더한다. 예를 들어 R7, Y7, R2, G7, R5 일 때 점수는 407(=7+400)점이다.
7. 카드 5장 중 2장의 숫자가 같고 또 다른 2장의 숫자가 같을 때 점수는 같은 숫자 중 큰 숫자에 10을 곱하고 같은 숫자 중 작은 숫자를 더한 다음 300을 더한다. 예를 들어, R5, Y5, Y4, G9, B4 일 때 점수는 354(=5X10+4+300)점이다.
8. 카드 5장 중 2장의 숫자가 같을 때 점수는 같은 숫자에 200을 더한다. 예를 들어, R5, Y2, B5, B3, G4 일 때 점수는 205(=5+200)점이다.
9. 위의 어떤 경우에도 해당하지 않을 때 점수는 가장 큰 숫자에 100을 더한다. 예를 들어, R1, R2, B4, B8, Y5 일 때 점수는 108(=8+100)점이다.

입력으로 카드 5장이 주어질 때, 카드 게임의 점수를 구하는 프로그램을 작성하시오. 두 가지 이상의 규칙을 적용할 수 있는 경우에는 가장 높은 점수가 카드 게임의 점수이다.

입력:

첫째 줄부터 다섯째 줄까지 한 줄에 카드 하나씩 입력된다. 카드의 색깔과 숫자 사이에는 빈 칸이 하나 있다.

출력:

한 줄에 카드의 점수를 출력한다.

풀이방법:

 주어진 규칙에 알맞게 점수계산을 하면 된다. 규칙 조건에 따라 중복으로 계산이 되는 경우가 존재하는데 조건문을 통해 최댓값을 가지도록 한다.

규칙을 크게 보면 다음과 같이 세 가지가 있다.

<색 조건>

1. 모두 같은 색을 가지는 가?

<숫자 조건>

2. 숫자가 연속 되는가?

3. 공통된 숫자가 K개 있다.

따라서 각 조건에 대해 다음과 같은 방법을 사용한다.

1. set 연산을 사용해 원소의 갯수가 1이면 모두 같은 색이다.

2. 가장 큰 값과 가장 작은 값의 차이가 4면 연속되어 있다.

3. 숫자가 key, 갯수가 value은 dict 자료형을 사용한다.

위 방법들 사용해서 해당하는 규칙을 찾고 그에 맞게 계산하면 된다.

문제링크:

www.acmicpc.net/problem/2621

문제:

암호화 방식 중에는 소수를 이용하는 것들이 많다. 보통은 매우 큰 두 개의 소수를 선택하고, 두 소수를 곱한 값을 암호화에서의 키로 사용하고는 한다. 이러한 방법이 좋은 이유는 일반적으로 매우 큰 수를 소인수분해 하는 것이 어렵기 때문이다.

소수를 택할 때 큰 수를 택하면, 이 둘을 곱해서 얻어지는 키 값도 커지게 된다. 하지만 그 반대는 성립하지 않을 수도 있다. 즉, 키 값이 매우 큰 경우에도 이를 소인수분해 하는 것은 쉬울 수도 있다.

따라서 암호문이 크랙되지 않도록 하기 위해서는, 키 값이 적절히 큰 수들의 곱으로 이루어져 있는지를 확인해야 할 필요가 있다. 키 값 K(4≤K≤10^100)와 정수 L(2≤L≤1,000,000)이 주어졌을 때, K를 인수분해 했을 때, 항상 L 이상의 값으로만 이루어져 있는지를 확인하고 싶다. 물론 인수분해 할 때 1로 나누는 경우는 고려하지 않는다.

예를 들어 K=143인 경우, 이는 11과 13의 곱으로 이루어져 있다. 즉, 이를 인수분해 하는 방법은 11×13, 143의 두 가지 경우뿐이다. 따라서 L이 11일 경우에는 인수분해 했을 때 나온 수들이 모두 L 이상이므로 좋은 경우지만, L이 12이상일 경우에는 좋은 암호가 아니다.

K와 L이 주어졌을 때, 좋은 암호인지 판단하는 프로그램을 작성하시오.

입력:

첫째 줄에 두 정수 K, L이 주어진다.

출력:

좋은 암호인 경우에는 GOOD을 출력한다. 나쁜 암호일 경우에는 BAD를 출력하고, K의 가장 작은 (1 아닌) 인수를 출력한다.

풀이방법:

K가 L 미만의 소수로 나눠지는지 확인하면 되는 문제다. 따라서 에라토스테네스의 체를 사용해서 L 미만의 소수를 찾은 뒤에 그 소수들로 K로 나눠본다.

나눠지면 BAD와 함께 그 수를 출력하고, 나눠지지 않는다면 GOOD을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/2061

문제:

알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다.

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 1 이상인 단어여야 한다. 이제 이렇게 나눈 세 개의 작은 단어들을 앞뒤를 뒤집고, 이를 다시 원래의 순서대로 합친다.

예를 들어,

• 단어 : arrested
• 세 단어로 나누기 : ar / rest / ed
• 각각 뒤집기 : ra / tser / de
• 합치기 : ratserde

단어가 주어지면, 이렇게 만들 수 있는 단어 중에서 사전순으로 가장 앞서는 단어를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 영어 소문자로 된 단어가 주어진다. 길이는 3 이상 50 이하이다.

출력:

첫째 줄에 구하고자 하는 단어를 출력하면 된다.

풀이방법:

반복문 두 개를 사용해서 주어진 조건대로 하나씩 단어를 만들면서 해당하는 단어가 사전상 먼저 인지 확인하면 된다.

문제링크:

www.acmicpc.net/problem/1251

문제:

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력:

첫째 줄에 최소 비교 횟수를 출력한다.

풀이방법:

최소한의 비교를 하기 위해서는 계속해서 가장 작은 두 수를 골라서 비교를 하는 것이 이득이다. 따라서 python의 heapq를 사용해 최소힙을 구성한다.

heappop을 사용해서 가장 작은 두 값을 뽑아내고, 이 둘을 합친 값을 다시 heap에 넣는다. 이를 heap에 하나의 원소가 남을 때까지 반복하면 최소 비교 횟수를 얻을 수 있다.

문제링크:

www.acmicpc.net/problem/1715

문제:

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.

A =>  < < < > < < > < >

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다. 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력:

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

출력:

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

풀이방법:

 처음에는 itertools의 permutation을 사용해서 풀려고 했으나, 메모리 초과가 발생했다. 아무래도 경우의 수가 엄청 많기 때문에 발생한 것 같았다.

 따라서 백트래킹(dfs)를 사용해서 효율적으로 구하려고 했다. visited 배열을 만들어서 사용한 숫자, 그렇지 않은 숫자를 구분했고, 빈 문자열로 시작했기 때문에 length==0이라는 조건을 넣어주게 되었다. is_possible 함수를 통해 부등호를 만족하는 조건의 숫자들을 구했으면 이를 answer 배열에 넣도록 한다. 

 이 때, answer 배열들의 숫자들은 작은 숫자부터 생성하기 시작했기 때문에 맨 처음에는 "부등호를 만족하는 가장 작은 숫자", 맨 마지막에는 "부등호를 만족하는 가장 큰 숫자"가 들어가 있게 된다. 따라서 이를 알맞게 출력하면 된다.

문제링크:

www.acmicpc.net/problem/2529

문제:

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력:

첫째 줄에 경우의 수를 출력한다.

풀이방법:

 포인터 두 개를 활용해서 해결할 수 있는 문제다. start와 end 포인터 두 개를 만든다. start가 문제의 i를 의미하고, j가 문제의 j를 의미하게 된다.

 이 두 포인터를 사용해서 구간 합을 얻고, 이 구간 합이 원하는 값 M보다 작다면 end 포인터를 증가시켜서 구간 합이 커지도록 한다. 만약 M보다 크거나 같다면, start 포인터를 증가시켜서 구간 합이 작아지도록 한다.

 두 포인터의 이동이 종료되는 조건은 end 포인터가 N이 될 때(IndexError가 발생하지 않게 하기 위함), 혹은 start 포인터가 end 포인터를 앞지를 때 종료하도록 한다. 

문제링크:

www.acmicpc.net/problem/2003

문제:

숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

다음은 나쁜 수열의 예이다.

• 33
• 32121323
• 123123213

다음은 좋은 수열의 예이다.

• 2
• 32
• 32123
• 1232123

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열은 1213121이다.

입력:

입력은 숫자 N하나로 이루어진다. N은 1 이상 80 이하이다.

출력:

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

풀이방법:

 dfs를 사용해서 수열에 숫자 하나씩을 붙여나가면서 좋은 수열인지 확인하고, 좋은 수열이라면 다시 붙이고, 그렇지 않다면 다른 숫자를 붙이는 방법을 사용하도록 한다.

 좋은 수열들 중 가장 작은 값을 찾아야 한다. 따라서 작은 값이 되기 위해서는 1로 시작해야 한다.

문제링크:

www.acmicpc.net/problem/2661

문제:

환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이어붙이고 그 끈을 다시 길이가 소수인 끈 두개로 정확히 나눌 수 있다면 두 사람은 환상의 짝꿍이라고 한다. 하지만 그들은 길이가 소수인 두개의 끈으로 나눌 수 있는지 판단하는 것이 어려워서 대부분 서로가 인연임을 모르고 그냥 지나간다고 한다. 애석하게도...

그런 그들을 위해서 어떤 두 사람이 환상의 짝꿍인지 판단하는 프로그램을 작성하라.

편의상 두 사람의 끈을 이어붙일 때와 나눌 때 손실되는 끈의 길이는 0이라고 가정한다.

입력:

첫째 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 500)가 주어진다.

둘째 줄부터 T개 줄에 두 사람이 가지고 있는 끈의 길이를 나타내는 정수 A, B가 공백으로 구분되어 주어진다. (1 ≤ A, B ≤ 2 × 10^12)

출력:

각 테스트 케이스마다 한 줄씩 두 사람의 끈을 이어붙이고 그 끈을 다시 길이가 소수인 두개의 끈으로 정확히 나눌 수 있다면 YES, 불가능하면 NO를 출력하라.

풀이방법:

**pypy3으로 통과한 코드입니다.**

 A와 B의 합이 두 개의 소수의 나누어지는지 완전알고리즘 방법으로 모두 찾는 것은 힘들다.(A,B는 최대 2x10^12)

따라서 '골드바흐의 추측'을 사용하면 경우의 수를 크게 줄일 수 있다.

 골드바흐의 추측은 2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다는 것이다. 즉, 두 수의 합이 2를 제외한 짝수라면 골드바흐의 추측으로 인해 두 소수의 합으로 나눌 수 있다. 그러므로 이제 두 수의 합이 홀수인 경우에 대해서만 생각하면 된다. (확인된 수치적 결과로는 10^18까지 확인되었다고 한다. 따라서 범위 안의 수들은 모두 골드바흐 추추측을 만족한다.)

 두 소수의 합이 홀수가 되기 위해서는 짝수 소수 + 홀수 소수 인 경우만 존재한다. 소수 중에서 짝수인 소수는 2만 존재하기 때문에 A+B-2가 소수인지만 확인하면 된다. 하지만 A와 B의 수가 매우 큰 수까지 존재하기 때문에 해당 수 까지 소수인지 확인하는 것은 어렵다.(혹은 메모리초과가 발생한다.) 따라서 소수를 판정하는 방법을 두 가지로 나눠서 파악한다.

 A+B의 합은 최대 4x10^12까지 가능하다. 그리고 일반적으로 소수를 판정하는 방법으로는 1부터 해당 수의 sqrt() 값까지 확인하면 된다. 즉, 4x10^12까지의 소수를 찾아놓는 것이 아닌 sqrt() 값인 2x10^6까지만 소수를 찾아서 효율성을 향상시키도록 한다. 2x10^6까지는 에라토스테네스의 체를 사용해서 소수를 찾아두고, 이 이상의 수가 들어오게 된다면, 찾아놓은 소수로 나눠서 나눠지는 수가 있는지 확인한다. 따라서 A+B-2가 소수라면 YES를 아니라면 NO를 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/15711

문제:

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

주어진 필드가 위의 그림과 같고, 예은이의 수색범위가 4라고 하자. ( 원 밖의 숫자는 지역 번호, 안의 숫자는 아이템 수, 선 위의 숫자는 거리를 의미한다) 예은이가 2번 지역에 떨어지게 되면 1번,2번(자기 지역), 3번, 5번 지역에 도달할 수 있다. (4번 지역의 경우 가는 거리가 3 + 5 = 8 > 4(수색범위) 이므로 4번 지역의 아이템을 얻을 수 없다.) 이렇게 되면 예은이는 23개의 아이템을 얻을 수 있고, 이는 위의 필드에서 예은이가 얻을 수 있는 아이템의 최대 개수이다.

입력:

첫째 줄에는 지역의 개수 n (1 ≤ n ≤ 100)과 예은이의 수색범위 m (1 ≤ m ≤ 15), 길의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로  각 구역에 있는 아이템의 수 t (1 ≤ t ≤ 30)를 알려준다.

세 번째 줄부터 r+2번째 줄 까지 길 양 끝에 존재하는 지역의 번호 a, b, 그리고 길의 길이 l (1 ≤ l ≤ 15)가 주어진다.

출력:

예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.

풀이방법:

플로이드-와샬 알고리즘을 적용해서 이 문제를 풀 수 있다. 플로이드-와샬 알고리즘은 주어진 그래프의 경로로 가중치를 초기화한 후 i에서 j로 가는 경로에 k가 추가 되었을 때, 이전의 경로의 가중치보다 작아지는지 확인하면 된다. 

플로이드-와샬로 초기화를 완료한 뒤에, 지역의 개수 n을 반복문으로 순회한다. 순회하면서 임계점에 해당하는 값인 m보다 작은 값들을 모두 더해주고, 마지막에 현재 시작한 지역의 값을 더해주도록 한다. 이 중 가장 큰 값을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/14938

문제:

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력:

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력:

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

풀이방법:

 이러한 문제는 최소 스패닝 트리를 사용해서 푸는 전형적인 문제다. Kruskal, Prim 알고리즘으로 풀 수 있으며, 이번 문제는 Prim 알고리즘을 활용해서 풀었다.

 Prim 알고리즘은 다음의 순서대로 작동한다.

1. 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다.
2. 그래프의 모든 변이 들어 있는 집합을 만든다.
3. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안
   1. 트리의 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 가장 가중치가 작은 변을 트리에 추가한다.

 이 알고리즘이 종료되었을 때 만들어진 트리는 최소 비용 신장 트리가 된다. [출처: Prim 알고리즘 위키피디아]

따라서 위 알고리즘대로 해당 노드로 이동하는 최소 비용을 의미하는 distance 배열을 INF로, 전체 가중치를 가지고 있는 vertice를 초기화 하고, 모든 컴퓨터를 방문했는지 확인할 수 있는 visited 배열을 만든다.

 이제 1번 컴퓨터(인덱스상 0번)를 임의로 선택하여 위 알고리즘대로 트리를 만들기 시작한다. 1번 컴퓨터로 향하는 distance는 0이다. (문제 조건 상 a와 b가 같을 수 있다고 하는데 큰 의미는 없는 것 같다.) distance와 visited 배열을 바탕으로 선택해야 하는 distance를 고른다.( 첫번쨰의 경우에는 당연히 1번 컴퓨터만 distance가 변경되었으므로 1번 컴퓨터다.) 1번 컴퓨터가 선택되었으므로, 이 컴퓨터와 연결 된 Edge들을 distance에 반영한다.

 위 과정을 모든 컴퓨터를 다 방문할 때까지 반복하며, 알고리즘이 종료되었을 때의 distance의 합이 최소 비용을 의미하게 된다.

문제링크:

www.acmicpc.net/problem/1922