CodeDrive

문제:

수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.

이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.

• 문자열의 뒤에 A를 추가한다.
• 문자열을 뒤집고 뒤에 B를 추가한다.

주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. 

입력:

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

출력:

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

풀이방법:

 S를 T로 바꾸는 방법에 대해 찾는 것이 아니라 T에서 S로 그리디하게 되돌아가는 방법으로 만들 수 있는지 없는지 확인한다.

 두 가지 연산은 맨 뒤에 A가 추가되거나 B가 추가된다. 따라서 매번 T의 맨 끝에 따라 연산을 수행하도록 한다. 맨 마지막이 A라면 A만 떼어내고, B라면 B를 떼어내고 뒤집어서 새로 T를 만들어내도록 한다.

 T와 S의 길이가 같아졌을 때, S와 T가 같다면 1을 같지않다면 0을 출력한다.

문제링크:

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

문제:

2007년 KOI에 N명의 학생들이 참가하였다. 경시일 전날인 예비소집일에, 모든 학생들은 자신이 N명 중에서 몇 등을 할 것인지 예상 등수를 적어서 제출하도록 하였다.

KOI 담당조교로 참가한 김진영 조교는 실수로 모든 학생의 프로그램을 날려 버렸다. 1등부터 N등까지 동석차 없이 등수를 매겨야 하는 김 조교는, 어쩔 수 없이 각 사람이 제출한 예상 등수를 바탕으로 임의로 등수를 매기기로 했다.

자신의 등수를 A등으로 예상하였는데 실제 등수가 B등이 될 경우, 이 사람의 불만도는 A와 B의 차이 (|A - B|)로 수치화할 수 있다. 당신은 N명의 사람들의 불만도의 총 합을 최소로 하면서, 학생들의 등수를 매기려고 한다.

각 사람의 예상 등수가 주어졌을 때, 김 조교를 도와 이러한 불만도의 합을 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에 걸쳐 각 사람의 예상 등수가 순서대로 주어진다. 예상 등수는 500,000 이하의 자연수이다.

출력:

첫째 줄에 불만도의 합을 최소로 할 때, 그 불만도를 출력한다.

풀이방법:

 각 학생들이 작성한 예상 등수를 바탕으로 정렬을 하고, 그와 동일하게 순위를 부여하는 것이 가장 사람들의 불만도를 최소로 하는 방법이다.

문제링크:

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

문제:

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1,1 -> 0)

입력:

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력:

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

풀이방법:

 그리디 방법이므로 현재 위치하고 있는 곳에서 A와 B를 비교해서 뒤집을지 결정해주면 된다. 왼쪽 위부터 오른쪽으로 한칸씩 미끄러져 가며 비교를 하고 맨 윗줄을 다 비교하면 그 아랫줄로 내려가서 비교를 해주도록 한다. 이렇게 하면 한 번 그 위치를 기준으로 뒤집은 경우에는 다시 그 칸을 뒤집진 않기 때문에 한 번 뒤집었던 부분을 다시 뒤집을 수 있다는 걱정을 할 필요 없다. 따라서 이렇게 행렬A를 탐색하며 다 뒤집은 다음에 행렬 B와 비교해서 일치한다면 연산의 최솟값을 출력하고 그렇지 않다면 -1을 출력하도록 하였다.

문제 링크:

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