CodeDrive

문제:

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

풀이방법:

 우선 N개의 재료들을 오름차순으로 정렬하고, 첫 값(start)과 마지막 값(end)에 포인터를 할당한다. 그리고 해당 위치에 있는 값들을 더하면서 M이 되는지 확인하고, 만약 M보다 크다면 end의 값을 줄이고, M보다 작거나 같다면 start를 하나 늘리도록 한다. 이 과정을 start와 end가 같아질 때까지 반복하도록 한다.(같은 순간에 종료)

문제링크:

https://www.acmicpc.net/problem/1940

문제:

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력:

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력:

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

풀이방법:

 우선 각 알파벳의 갯수를 count를 한다. 이 때, 홀수 개인 알파벳이 한 개만 있거나 없을 경우에만 팰린드롬을 만들 수 있다. 홀수 개인 알파벳이 하나만 있을때만, 가운데에 배치하여 팰린드롬을 만들 수 있기 때문이다. 따라서 이 조건을 사용해서 우선적으로 필터링해주도록 한다.

 만들 수 있는 경우에는 알파벳을 사전순으로 정렬한 뒤 만들어나가기 시작한다. 각 알파벳의 갯수 M/2개를 문자열에 이어붙이고, 모든 문자열을 순회한 경우에는 다시 역순으로 M/2개를 문자열에 이어 붙이도록 한다. 이 때, 홀수 개인 알파벳이 있었다면, 역순으로 진행하기 전에 먼저 붙이도록 한다.

문제링크:

https://www.acmicpc.net/problem/1213

문제:

선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다.

호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다. 

선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다.

어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다.

패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.

파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, "abcd", "ad", "anestonestod"는 모두 패턴 "a*d"와 일치한다. 하지만, "bcd"는 일치하지 않는다.

패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 파일의 개수 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다.

다음 N개 줄에는 파일 이름이 주어진다. 파일 이름은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력:

총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다.

참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다.

풀이방법:

 패턴과 일치하는 문자열을 찾기 위해 사용할 수 있는 라이브러리로 정규표현식이 있다. 따라서. 주어진 패턴을 정규표현식 형태로 변경하여 출력을 하도록 한다.

 문제에서 주어진 *와 같은 역할을 하는 것은 정규표현식에서 . 에 해당한다. 따라서 replace를 사용하여 이를 변경해주도록 한다. 그리고 패턴이 변수에 할당된 상태로 사용해야 하기 때문에 formatting을 사용하여 string 형태로 사용할 수 있도록 한다. 이 패턴과 추가적으로 ^(맨 앞임을 의미), $(맨 끝임을 의미)를 사용하여 패턴을 마무리하도록 한다. 들어 오는 입력대로 패턴과 일치하는지 확인하여 알맞은 출력을 하도록 한다.

문제링크:

https://www.acmicpc.net/problem/9996

문제:

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

입력:

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력:

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

풀이방법:

 이 문제를 해결하기 위해서 다음과 같은 하나의 가정을 하도록 한다. Sn을 n까지의 저울추를 더한 값이라고 하고, An을 저울추라고 하자. 그럼 Sn+2 <= A(n+1)가 될 때, Sn+1은 측정할 수 없는 최솟값이 된다. 이러한 가정이 가능한 이유는 Sn이 Sn까지 무게를 측정할 수 있다는 의미를 가지기 때문이다.

 따라서 오름차순으로 정렬한 뒤에 저울추를 하나씩 올리면서 가정에 도달할 때까지 반복하도록 한다.

문제링크:

https://www.acmicpc.net/problem/2437

문제:

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

• 다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

(2) 2번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

(3) 3번 마을에 도착하면

• 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
• 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

(4) 4번 마을에 도착하면

• 받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력:

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

출력:

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

풀이방법:

입력으로 들어오는 값들을 적절히 잘 정렬하는 것이 중요하다. 입력들을 시작하는 마을로 정렬하게 된다면 다음과 같은 문제가 발생할 수 있다.

C = 20

1 4 30

2 3 20

3 4 20

 이 경우에는 1번 마을에서 택배를 싣고 출발하지만, 중간의 마을에서는 택배를 싣지 못하게 된다. 하지만 이 케이스의 정답은 1번 마을에서는 택배를 적재하지 않고, 2번마을, 3번 마을에서 각각 20씩 싣는 것이 최대 박스 수를 얻을 수 있다. 

 따라서 시작하는 마을을 기준으로 정렬하는 것이 아닌 도착하는 마을을 기준으로 정렬을 하도록 한다. 그리고 각 마을마다 가능한 용량 C를 초기화하고, 한 박스를 적재할 때마다 감소시키며, 최대한 많은 박스를 싣도록 한다.

문제링크:

https://www.acmicpc.net/problem/8980

문제:

바퀴와 벨트를 이용하여 실험을 할 수 있는 과학 교구가 있다. 이 교구에는 다양한 종류의 바퀴와 벨트, 그리고 여러 개의 바퀴를 서로 다른 곳에 꽂을 수 있는 교구판이 포함되어 있다.

교구판에는 바퀴를 꽂을 수 있는 축들이 한 줄로 늘어서 있다. 모든 축에 바퀴를 꽂았을 때 바퀴끼리 부딪치지 않도록 축과 축 사이는 충분히 멀리 떨어져 있다. 각 축에는 바퀴가 하나씩 꽂혀있다. 바퀴는 왼쪽부터 순서대로 1번부터 차례대로 번호가 매겨져 있다. 

교구판에서 바로 옆에 있는 두 개의 바퀴는 항상 하나의 벨트로 연결해야 하는데, 이때 벨트를 0자 형태로 연결할 수도 있고 8자 형태로 한번 꼬아서 연결할 수도 있다. 그리고 한쪽 바퀴가 회전하게 되면 벨트로 연결된 다른 바퀴도 회전하게 되는데 이때 두 바퀴의 크기의 차이에 따라 두 바퀴의 회전수가 서로 다를 수 있다. 

다음 예는 3개의 벨트와 4개의 바퀴에 대한 정보가 주어진 경우이다. 이때 벨트 형태는 0자 형태(안꼬인 형태)면 0으로, 8자 형태(꼬인 형태)면 1로 나타낸다.

이 경우, 벨트 1은 바퀴 1과 바퀴 2를 0자 형태로 연결하며 바퀴 1이 1번 회전하는 동안 바퀴 2는 2번 회전하게 된다. 즉, 바퀴 1을 시계 방향으로 1회전시키면 바퀴 2는 시계 방향으로 2회전하게 된다. 

벨트 2는 바퀴 2와 바퀴 3을 꼬인 형태로 연결하며 바퀴 2가 1번 회전하는 동안 바퀴 3은 5번 회전하게 되므로, 바퀴 2를 시계 방향으로 1회전시키면 바퀴 3은 반시계 방향으로 5회전하게 된다. 

벨트 3은 바퀴 3과 바퀴 4를 0자 형태로 연결하며 바퀴 3이 2번 회전하는 동안 바퀴 4는 1번 회전하게 되므로, 바퀴 3을 시계 방향으로 2회전시키면 바퀴 4는 시계 방향으로 1회전하게 된다. 

따라서, 처음에 바퀴 1을 시계방향으로 1회전시키면 바퀴 2와 바퀴 3을 거쳐 결국 바퀴 4는 반시계방향으로 5회전하게 된다. 

벨트로 연결된 바퀴들의 회전수의 비와 벨트의 형태가 순서대로 주어졌을 때, 첫 번째 바퀴가 시계 방향으로 분당 1회전을 하는 경우 마지막 바퀴의 회전방향과 분당 회전수를 출력하는 프로그램을 작성하시오.

입력:

첫 줄에는 벨트의 개수를 나타내는 자연수 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 M개의 줄에는 1번 벨트부터 순서대로 벨트로 이어진 두 바퀴의 회전수의 비를 나타내는 두 개의 양의 정수 a, b와 벨트의 형태 0 또는 1이 한 줄에 주어진다. 즉, i번 벨트의 경우, i번 벨트로 이어진 두 바퀴 i와 i+1에 대해 바퀴 i가 a번 회전하는 동안 바퀴 i+1이 b번 회전하고 i번 벨트의 형태가 s(안꼬인 형태는 0, 꼬인 형태는 1)라면 a와 b, 그리고 s가 한 줄에 주어진다. 이때 모든 바퀴의 분당 회전수는 109 이하의 양의 정수로 결정되도록 입력이 주어진다. a, b는 109 이하의 양의 정수이고, a와 b는 서로소이다.

출력:

M+1번 바퀴의 회전 방향(시계방향은 0, 반시계방향은 1)과 분당 회전수를 한줄에 출력한다. 

풀이방법:

 순차적으로 벨트를 이동하며 회전수를 구하면 된다. 회전방향과 같은 경우에는 1이 들어온 경우에만 바뀌므로 나머지 연산을 통해 방향을 바꾼다.

 회전수를 구하는 방법은 b/a를 곱하는 것인데, 이 때, ans*=(b/a)와 같이 하면 에러가 발생하게 된다. 따라서 ans = (ans*b)/a와 같은 방법으로 회전 수를 구하도록 한다.

문제링크:

https://www.acmicpc.net/problem/10834

문제:

아래 mystery.c는 입력파일 X를 읽어서 그 안에 기록된 N개의 정수를 배열 NUM에 저장한 뒤에 이 N개의 수를 어떤 순서에 따라서 화면에 출력하는 프로그램이다. mystery.c가 X를 입력으로 받아 화면에 출력한 결과를 Y라고 하자.

#include <stdio.h>
int NUM[101] ;
FILE *fin ;
int main(){
    int i, token,N ;
    int count=0, from= 0, value ;
    fin = fopen("X","r");
    fscanf(fin,"%d",&N);
    for(i=0; i<N; i++){
        fscanf(fin,"%d",&token);
        NUM[i]= token;
    } /* end of for */
    printf("%d\n", N ) ;
    value = NUM[ from ] ;
    while( count < N ) {
        while( value == 0 ) { 
            from = (from+1)%N; 
            value = NUM[ from ] ; 
        } /* end of inner while */ 
        printf("%d ", value ) ;
        count++ ;
        NUM[ from ] = 0 ; 
        from = (value +from )% N ; 
        value = NUM[ from ] ; 
    } /* end of outer while */
    return(0);
} /* end of main() */

여러분은 mystery.c에서 생성된 Y를 파일로 받아서 그것의 입력에 해당하는 X를 찾아내는 프로그램을 작성해야 한다. 

입력:

첫 줄에는 정수 N (1 ≤ N ≤ 30)이 주어진다. 그리고 두 번째 줄에는 100이하 양의 정수 N개가 빈칸을 사이에 두고 모두 나열되어 있다. 단 그 정수 중에는 같은 수가 있을 수도 있다.

출력:

첫 줄에는 정수 N이 제시되어 있고, 그 다음 줄에는 N개의 양의 정수가 빈칸을 사이에 두고 기록되어 있어야 한다. 만일 입력을 생성하는 mystery.c의 입력파일 X가 없는 경우에는 음수인 -1 을 첫 줄에 출력하면 된다.

풀이방법:

주어진 코드를 역추적할 수 있도록 구현해야 하는 문제다. X가 없는 경우는 없기 때문에 -1은 고려하지 않아도 된다.

문제링크:

https://www.acmicpc.net/problem/8981

문제:

기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.

기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.

1. 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다.
2. 소형 기관차 3대를 이용하여 최대한 많은 손님을 목적지까지 운송하도록 한다. 각 객차 마다 타고 있는 손님의 수는 미리 알고 있고, 다른 객차로 손님들이 이동하는 것은 허용하지 않는다.
3. 각 소형 기관차는 번호가 연속적으로 이어진 객차를 끌게 한다. 객차는 기관차 바로 뒤에 있는 객차부터 시작하여 1번 부터 차례로 번호가 붙어있다.

예를 들어 기관차가 끌고 가던 객차가 7칸이고, 소형 기관차 1대가 최대로 끌 수 있는 객차 수는 2칸이라고 하자. 그리고 1번 부터 7번까지 각 객차에 타고 있는 손님의 수가 아래 표와 같다고 하자. 괄호속에 있는 숫자는 객차 번호를 나타낸다.

(1)(2)(3)(4)(5)(6)(7)

소형 기관차 3대는 각각 1-2번, 3-4번, 그리고 6-7번 객차를 끌고 가면 손님 240명을 운송할 수 있고, 이보다 많은 수의 손님을 운송할 수 없다.

기관차가 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수, 그리고 소형 기관차가 최대로 끌수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있는 손님의 수는 100명 이하이고, 입력되는 숫자들 사이에 빈칸이 하나씩 있다. 셋째 줄에는 소형 기관차가 최대로 끌 수 있는 객차의 수가 입력된다. 그 수는 기관차가 끌고 가던 객차 수의 1/3보다 적다.

출력:

한 줄에 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 출력한다.

풀이방법:

점화식을 생성해서 DP로 해당 문제를 풀 수 있다. DP는 다음과 같이 정의한다.

• DP[N][M]: 소형기관차 N대를 운행할 때 M번째 객차를 선택했을 때 최대로 운송 가능한 손님 수

따라서 점화식은 다음과 같다.

DP[N][M] = max( DP[N][M-1], DP[N-1][M-limit] + sum(numbers[M-limit+1:M+1]))

점화식을 사용해서 문제의 예제에 대입하면 다음과 같이 DP 테이블을 채워나갈 수 있다.

예시를 참고하여 어떠한 원리로 동작하는지 알아보도록 한다.

• DP[1][2] = max(DP[1][1], DP[0][2-2] + sum(numbers[2-2+1:2+1]))
  • DP[1][1], DP[0][0]는 둘 다 0이기때문에, sum만 계산하면 되므로 35+45다.
• DP[3][6] = max(DP[3][5], DP[2][6-2] + sum(numbers[6-2+1:6+1])
  • DP[3][5]는 0이므로, 뒷 항에 의해 결된다. DP[2][6-2]는 75+60이고, 여기에 30+45를 더해준다.

점화식이 의미하는 것은 현재 운행하고 있는 소형 기관차가 이전의 객차를 변경없이 유지했을 때(DP(N][M-1]), N번째 소형 기관차를 객차를 선택하기 전에 N-1번째 소형기관차를 유지하면서(DP[N-1][M-limit]) N번째 소형기관차가 M번째 소형기관차를 선택했을 때(sum(numbers[M-limit+1:M+1]))를 비교하는 것이다.

문제링크:

https://www.acmicpc.net/problem/2616

문제:

N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 번호의 스위치와 전구는 전선으로 서로 연결되어 있다.

하나의 스위치를 누르면 그 스위치와 연결된 전구에 불이 들어오게 된다. 두 개 이상의 스위치를 같이 누르는 경우, 전선이 서로 만나면 만난 전선에 연결된 전구들의 불은 켜지지 않는다.

위 그림에서 1번과 4번의 스위치를 같이 누르면 1번과 4번의 전구에는 불이 켜지지만, 1번과 2번의 스위치를 같이 누르면 1번과 2번 전구의 불은 켜지지 않는다. 1번과 3번 그리고 5번 스위치를 같이 누르면 전선이 만나는 1번과 5번 전구는 켜지지 않지만 3번 전구는 켜지게 된다.

여러분이 할 일은 가장 많은 전구가 켜지도록 스위치를 누르는 것이다. 위 그림에서는 3번과 4번 그리고 5번 스위치를 누르는 경우와 1번과 3번 그리고 4번을 누르는 경우에 세 개의 전구가 켜지게 되고, 이 두 가지 경우가 가장 많은 전구가 켜지는 경우이다.

스위치의 번호순서와 전구의 번호순서가 주어질 때, 어떤 스위치를 누르면 가장 많은 전구가 켜지는지를 알아내는 프로그램을 작성하시오.

입력:

첫 번째 줄에는 스위치의 수(전구의 수)를 나타내는 정수 N (1 ≤ N ≤ 10,000)이 주어진다. 두 번째 줄에는 N개의 스위치 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다. 세 번째 줄에는 N개의 전구 번호들이 위에서부터 순서대로 빈칸을 사이에 두고 주어진다.

출력:

첫 번째 줄에는 가장 많은 전구가 켜지게 하는 스위치의 수를 출력한다. 두 번째 줄에는 눌러야 하는 스위치의 번호를 오름차순(번호가 커지는 순서)으로 빈칸을 사이에 두고 하나의 줄에 출력한다. 단, 두 번째 줄에 출력할 수 있는 답이 두 가지 이상일 때에는 그 중 한 가지만 출력한다.

풀이방법:

 겹치지 않도록 최대한 많이 선택해야 하는 문제다. 이는 곧 가장 긴 증가하는 부분 수열(LIS) 문제와 같다. 따라서 LIS 알고리즘을 사용하여 가장 긴 증가하는 부분 수열을 찾으면서 그 부분 수열의 번호들도 같이 찾는 문제에 해당한다.

 LIS 문제를 해결하는 방법에는 여러가지가 있지만, 이 문제에서는 bisect를 이용했다. 이 방법의 핵심은 최대한 작은 수들을 고르는 것이 가장 긴 증가하는 부분 수열을 만들기 유리하다는 것이다. 1 2 7 이라는 부분 수열과 1 2 4 이라는 부분 수열이 있을 때 후자의 경우가 더 긴 부분 수열을 만들 확률이 높다는 것이다. 따라서 입력으로 들어오는 배열에서 bisect을 이용하여 계속해서 배열을 최신화한다.

하지만 이 때 만드는 배열은 실제 가장 긴 증가하는 부분 수열은 아니다. 이는 길이만을 알 수 있기 때문에, 만드는 동시에 위치 정보도 같이 추가하여 마지막에 실제 가장 긴 부분수열을 찾을 수 있도록 한다. 이 때 사용하는 것이 idx 배열이며 , start의 각 원소가 몇 번째 자리에 들어가는지에 대한 여부다. idx=[0,0,1,1,2]라는 것은 2가 0번째, 4가 0번째, 1이 1번째, 5가 1번째, 3이 2번째 자리에 각각 들어가게 된다는 것이다. 따라서 역순으로 idx 배열을 탐색하면서 2, 1, 0이 먼저 나오는 순서로 넣는 것이 최종 답에 해당한다. (나중에 들어간 것이 마지막에 남아 있는 수들이기 때문)

문제링크:

https://www.acmicpc.net/problem/2550

문제:

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며 종류가 같은 주사위도 있을 수 있다.

그림 1

출력:

첫줄에 한 옆면의 숫자의 합이 가장 큰 값을 출력한다.

풀이방법:

 주사위는 상하로 연결되어 있기 때문에, 이를 위한 새로운 인덱스가 필요하다. 따라서 각 인덱스별로 연관있는 면의 인덱스를 담고 있는 dict을 만들도록 한다.

 그리고 첫 밑면에 따라 모든 경우의 수를 고려할 수 있도록 구현하도록 한다. 1번 주사위에 따라 2번부터 주사위가 결정되기 때문이다. 밑면의 숫자를 고르면 자동으로 윗 숫자가 결정되게 되고, 옆면의 숫자는 회전이 가능하기 때문에 남은 숫자 중에 max 값을 고른다.

 그 뒤로는 첫 주사위의 윗면의 숫자로 다음 주사위의 아래 인덱스가 결정되기 때문에 주사위는 순차적으로 주사위를 올리면서 옆면 중  max 값을 찾으면 된다.

문제링크:

https://www.acmicpc.net/problem/2116