CodeDrive

문제:

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다.

위의 상태에서 K = 1인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

 K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력:

첫 줄에 두 정수 N과 K가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.

출력:

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다

풀이방법:

 사람을 기준으로 -K인 인덱스부터 햄버거를 우선 배정하는 그리디 알고리즘을 사용한다. 인덱스를 사용하기 때문에 IndexError가 발생하지 않도록 주의한다.

문제링크:

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

문제:

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력:

첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

풀이방법:

X인 부분을 그리디하게 채워나가도록 한다. X가 4개이상이라면 AAAA로 채우고, 4개 미만이라면 BB로 채우도록 한다. 이 때, X가 남은 경우 혹은 X가 부족한 경우가 덮을 수 없는 케이스라고 판단한다.

문제링크:

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

문제:

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력:

첫째 줄에 줄을 선 순서대로 키를 출력한다.

풀이방법:

 이 문제는 그리디하게 채워나가는 것을 목표로 한다. 우선 N과 같은 길이의 0으로 채워진 배열(answers)을 생성한 후 다음과 같은 조건으로 채워나간다.

1. 현재 answers 인덱스에 이미 사람이 채워져 있는가?
2. 만약 비어있다면, 내가 들어갈 차례인가?
   1. 비어있던(answers가 0) 횟수가 내 순서와 같은가?

 즉, answers가 0인 경우에 자기보다 큰 사람이 들어갈 자리라고 생각하며, 이 자리를 미리 고려하면서 빈 자리에 들어가는 것을 선택한다.

문제링크:

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

문제:

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

출력:

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

풀이방법:

바구니의 너비가 있기 때문에 사과를 양 끝에 걸치게 받는 것이 가장 조금 이동하면서 사과를 받는 방법이다. 따라서 바구니의 양 끝의 index를 기억하면서 사과가 떨어지는 지점과의 차이를 더해나가도록 한다.

사과가 바구니의 오른쪽이면 바구니의 오른쪽과의 차이를 , 왼쪽이라면 바구니의 왼쪽과의 차이를 계산하면서 바구니도 같이 이동시키도록 한다.

문제링크:

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

문제:

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

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

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

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

입력:

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

출력:

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

풀이방법:

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

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

문제링크:

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

문제:

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

무게가 양의 정수인 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

문제:

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력:

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

출력:

첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

풀이방법:

 앞에서부터 하나씩 비교해보면서 숫자가 달라지는 횟수를 측정하고 더 작은 변경으로 선택하면 된다. 비교를 할 때, 길이-1의 값까지만 측정했기 때문에 맨 마지막 값의 count도 더해주도록 한다. 만약 하지 않는다면, 10010과 같은 케이스일 때, 오류가 발생할 수 있다.

문제링크:

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

문제:

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

입력:

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

풀이방법:

 처음에 모든 물병에 물이 1리터씩 들어있고, 이를 한 물병에 합치는 과정을 하는 과정은 이진수를 더하는 것과 같다. 예를 들어, N=3, K=1일 때를 보면, 물병이 3개가 있다는 것은 이진수로 보면 11(3)과 같고, 실제로 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남아있다. 만약 상점에서 한 개의 물병을 산다면, 4리터가 들어있는 물병 한 개를 만들 수 있다. (11+1 =100) 

 즉, 이 문제는 주어진 N을 2진수로 변경한 뒤에 1씩 더하면서, 더한 값의 이진수 값에 1의 값이 K개 있을 때까지 반복하여 더해주면 된다.

문제링크:

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

문제:

어떤 원본 문자열 S가 주어졌을 때, 이 문자열의 부분을 복사하여 P라는 새로운 문자열을 만들려고 한다. 복사를 할 때에는 copy(s, p) 이라는 함수를 이용하는데, 이는 S의 s번 문자부터 p개의 문자를 P에 복사해서 붙인다는 의미이다.

예를 들어 S="abaabba", P="aaabbbabbbaaa"인 경우를 생각해 보자. 이때는 copy(3, 2), copy(4, 3), copy(2, 2), copy(5, 2), copy(2, 3), copy(1, 1) 를 수행하여 P를 만들 수 있다. 각 단계별로 P는 "aa", "aaabb", "aaabbba", …와 같이 변하게 된다.

이와 같은 copy 연산을 이용하여 S에서 P를 만들려고 하는데, 이때 가능하면 copy 함수를 조금 사용하려고 한다.

S와 P가 주어졌을 때, 필요한 copy 함수의 최소 사용횟수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 S, 둘째 줄에 P가 주어진다. S와 P는 영어 대소문자와 숫자로만 되어 있다. S의 길이는 1,000을 넘지 않으며, P의 길이는 1,000을 넘지 않는다. copy함수만을 이용하여 S에서 P를 만들어낼 수 없는 경우는 입력으로 주어지지 않는다고 가정하자. 각 문자열은 최소한 한 개의 문자로 이루어져 있다.

출력:

첫째 줄에 copy 함수의 최소 사용횟수를 출력한다.

풀이방법:

 P에 있는 부분 문자열을 S에서 그리디하게 찾아내어 이 문제를 해결하도록 한다.

찾으려는 P의 문자를 S에서 찾은 뒤에 그 지점으로부터 얼마나 많이 일치하는지 확인한다. 예를 들어 S="abaabba", P="aaabbbabbbaaa" 일 때, P의 첫 문자는 'a'이며, S에서는 a가 0, 2, 3, 6 번째에 위치하고 있다. python의 find 함수를 이용하여 a의 위치를 확인하고, P와 S 에서 동시에 포인터를 이동하며 얼마나 많이 일치하는지 찾는다. 다음 탐색은 일치하는 수 만큼 P의 포인터를 이동시킨다. 이 경우에는 S의 2번째에서 aa가 가장 길게 일치하므로, P의 2번째 인덱스부터 다음 탐색을 시작한다.

문제링크:

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