CodeDrive

문제:

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

먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다. 각각은 적어도 길이가 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

문제:

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력:

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력:

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

풀이방법:

**python3이 아닌 pypy3으로 통과한 문제입니다.**

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

이 과정을 마친 후에 a to b가 inf가 아니면 -1을, b to a가 inf가 아니면 1을 inf면 0을 출력하도록 한다.

문제링크:

www.acmicpc.net/problem/1613

문제:

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력:

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다.

출력:

가능한 모든 비밀번호의 개수를 출력한다.

풀이방법:

 처음에는 dfs를 활용한 백트래킹 방법으로 풀었다가 시간초과가 발생했다. 다른 방법을 생각해보던 중 수학적으로 풀 수 있음을 알게 되었다.

 따라서 포함배제의 원리를 사용해서 이 문제를 푼다. 문제에서 주어지는 n과 m만을 사용해서 풀수 있다.

m개의 수를 반드시 포함하는 경우의 수를 구하기 위해서 전체 가능한 경우의 수에서 m개의 수를 포함하지 않는 경우의 수를 빼는 것으로 구한다. 즉 다음과 같다.

비밀번호에 들어가는 수 m을 반드시 포함하는 비밀번호의 수 = 전체 비밀번호의 수 - m개의 수가 포함되지 않은 비밀번호의 수

전체 경우의 수는 10^n가 된다. m개의 수가 포함되지 않은 비밀번호의 수는 포함배제의 원리를 사용해서 구하도록 한다. 즉 구하는 식은 다음과 같이 된다.

answer = 10^n - mC1*9^n+mC2*8^n-mC3*7^n+.....

문제링크:

www.acmicpc.net/problem/13908