CodeDrive

문제:

 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 두 정수 L, C가 주어진다. (3<=L<=C<=15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력:

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

풀이 방법:

 재귀적인 방법으로 암호를 만들고, 이 암호가 옳은 암호인지 판단하는 check라는 함수를 만들었다. 암호를 만들다가 길이가 L이 된다면 check로 옳은 암호인지 판단을 하고 맞다면 출력, 아니면 끝내도록 했다.

문제링크:

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

문제:

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Ski이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1,2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

•  스타트 팀: S12+S21 = 1+ 4 = 5
•  링크 팀: S34 + S43 = 2 + 5 = 7

1,3 번이 스타팀, 2,4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

•  스타트 팀: S13+S31 = 2+ 7 = 9
•  링크 팀: S24 + S42 = 6 + 4 = 10

 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1,4번이 스타트 팀, 2,3 번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6의 되어서 차이가 0이 되고 이 값이 최소이다.

입력:

첫째 줄에 N(4<=N<=20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력:

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

풀이 방법:

 N은 최대 20이므로 나올 수 있는 조합의 경우의 수는 20C10이다. 이 정도의 수를 반복하는 것은 충분히 가능하기 때문에 브루트포스로 풀어도 상관없을 것 같았다. 

 우선 python의 itertools를 사용해서 나올 수 있는 조합을 만들었다. 그리고 set을 사용해서 스타트팀과 링크 팀으로 구분을 했고, 스타트팀과 링크 팀을 이중 반복문을 통해서 시너지의 합을 구했다. 그리고 시너지간의 차를 배열에 담았다.위 작업을 모두 마치고 나서 배열의 min을 출력하도록 하였다.

문제 링크:

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

문제:

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N()<=N<=100,000)에 있고, 동생은 점 K(0<=K<=100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력:

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력:

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

풀이 방법:

 여러 행위를 할 수 있는데 가장 빠른 방법을 찾는 문제는 대부분 BFS로 풀리는 경우가 많다. 따라서 이 문제도 X-1, X+1, 2X로 이동할 수 있는데 가장 빠른 시간을 찾기 때문에 BFS로 풀어야 한다.

 한 layer마다 Queue의 값에 따라 이동할 수 있는 위치를 새로 queue에 넣는다. 이 과정을 반복하다가 원하는 위치로 이동했다면(dist[k]의 값이 갱신 되었다면) queue를 종료하도록 해서 답을 출력하도록 했다.

문제 링크:

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

문제:

아래의 그림과 같이 높은 빌딩 사이를 따라 좁은 길이 나있다. 두 개의 사다리가 있는데 길이가 x인 사다리는 오른쪽 빌딩의 아래를 받침대로 하여 왼쪽 빌딩에 기대져 있고 길이가 y인 사다리는 왼쪽 빌딩의 아래를 받침대로 하여 오른쪽 빌딩에 기대져 있다. 그리고 두 사다리는 땅에서부터 정확하게 c인 지점에서 서로 교차한다. 그렇다면 두 빌딩은 얼마나 떨어져 있는 걸까?

입력:

첫째 줄에 차례대로 x,y,c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있다.

출력:

두 빌딩사이에 너비가 되는 수치를 출력한다. 절대/상대 오차는 10^-3까지 허용한다.

풀이방법:

 이분 탐색을 기반으로 하지만 수학적인 내용이 더 많이 들어가는 문제인 것 같다. 문제의 기본 틀은 두 빌딩 사이의 거리를 d라고 했을 때, 이를 이분 탐색으로 값을 바꾸어 간다. 임의의 d에 따라서 사다리가 교차하는 높이 h가 달라질 것이다. 따라서 이분탐색을 통해서 그 중 c와 같아지는 d를 찾도록 한다.

 임의의 d에 따라서 h를 구하는 방법은 수학의 닮음을 사용하도록 해야 한다. 사다리가 교차하는 높이를 h라 하고 선을 다음과 같이 그리면 닮음 꼴인 직각 삼각형을 얻을 수 있다.

h라는 직선이 생김에 따라 d도 d1과 d2로 나뉘게 될 것이고, h1과 h2도 다음과 같이 정의를 할 수 있을 것이다.

그러면 빗변이 x인 삼각형과 y인 삼각형에 각각 다음과 같은 닮음비를 얻을 수 있다.

 우리가 최종적으로 원하는 변수는 h이기 때문에 h=( ~ ) 와 같은 형태로 변형시켜야 할 것이다. 그러기 위해서는 d1+d2 = d임을 알고 있기 때문에 이를 활용해서 변수를 줄이도록 하자.

그러기 위해서는 일단 닮음비를 정리해서 d1과 d2에 관한 식으로 만들었다. 그리고 난 뒤에 위 두 식을 더한다면 d1과 d2를 d로 바꿀 수 있게 될 것이다.

 이제 양변을 각각 d로 나눌 수 있을 것이다. d는 두 빌딩 사이의 거리이므로 0을 초과한 거리일 것이다. 따라서 양변을 나누는 것에 문제가 없다.

 그러면 위 그림의 제일 위의 식과 같이 얻을 수 있을 것이고 좌변을 h에 대해서 묶을 수 있게 될 것이다. 좌변을 h로 묶고 난 뒤에 남은 것들을 우변으로 넘겨준다면 이를 h에 대한 식으로 만들 수 있을 것 이다. 따라서 위 그림의 두번째와 세번째 식은 그 과정을 담고 있다.

 h1과 h2는 x, y, d로 이루어진 변수이기 때문에 정확한 값을 계산할 수 있다. (d는 이분 탐색으로 정해진 값이다.) 따라서 h의 값을 구할 수 있을 것이고 이를 c와 비교하면서 c에 근접하게 d를 이분탐색으로 찾을 수 있을 것이다.

그렇게 찾은 mid값을 소숫점 셋째 자리까지 반올림해서 출력하도록 한다.

문제링크:

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

문제:

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=2,000,000,000)과 M(1<=M<=10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력:

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

풀이 방법:

이분 탐색을 사용해서 풀어야 하는 문제이다. 항상 이러한 이분 탐색을 사용해서 푸는 문제들은 찍어서 최적의 값을 맞춰나간다 라는 느낌이 강하다. 따라서 이 문제도 역시 일정 값을 찍어서 근처로 구하고 그 값으로 부터 놀이기구의 번호를 찾도록 하였다.

문제링크:

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

문제:

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

문제:

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이라는 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력:

N을 입력받는다. N은 최대 10^5개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력:

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

풀이방법:

 30의 배수가 되기 위해서는 10의 배수의 특징과 3의 배수 특징을 모두 가지고 있어야 한다. 10의 배수가 되려면 자릿수의 맨 끝이 0이 되어야 한다. 3의 배수가 되려면 각 자리를 다 더했을 때 3의 배수가 되어야 한다. 따라서 숫자에 0이 존재하고 각 자리를 모두 합했을 때 3의 배수라면 30의 배수를 만들 수 있다.

 따라서 30의 배수중 가장 큰 수를 원하기 때문에 각 자리를 리스트의 원소로 가지고 있는 배열을 역순으로(내림차순으로) 정렬한 뒤에 붙이는 것이 가장 큰 값이 될 것이다.

문제링크:

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

문제:

백준대학교에는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다.(왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다.

그런데 올해에는 대회에 참여하라는 학생들 중 K명을 반드시 인턴쉽 프로그램에 참여하라는 학교의 방침이 생기게 되었다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

입력:

첫째 줄에 N,M,K가 순서대로 주어진다 (0<=M<=100),(0<=N<=100),()<=K<=M+N)

출력:

만들 수 있는 팀의 최댓값을 출력하면 된다.

풀이 방법:

 인턴쉽에 K명이 반드시 참가해야하므로 이 인원을 먼저 빼도록 한다. 따라서 현재 남자와 여자 인원이 있을 때 만들 수 있는 팀이 있을 때 남는 인원들을 한명씩 인턴쉽으로 빼도록 한다. 이렇게 모두 인턴쉽에 K명을 모두 배정하고 난 뒤에 남은 사람들로 팀의 수를 출력하도록 한다.

문제 링크:

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

문제:

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)을 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0,1,2,4,3,5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 =15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야 한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력:

첫째 줄에 수열의 크기 N이 주어진다. N은 10,000보다 작다. 둘째 줄부터 N개의 줄에, 수열에 각 수가 주어진다. 수열의 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

출력:

수를 적절히 묶어 그 합이 최댓값을 출력한다. 정답은 항상 2^31보다 작다.

풀이 방법:

 합이 최댓값이 되도록 만들기 위해서는 양수는 양수끼리 곱해야 하고, 음수는 음수와 곱해서 양수가 되도록 만들어야 한다. 또한 작은 수와 곱하기 보다는 절대값이 큰 값들끼리 묶어야 합이 최댓값이 될 것이다. 따라서 수를 받을 때 양수와 음수로 나누어서 받도록 한다.

 그리고 값 중에서 1과 0은 최댓값으로 만들 때 방해가 되는 항목들이다. 0과 함께 묶으면 그 값은 0이 되어버려 사용할 수 없게 된다. 따라서 이는 음수가 홀수일 때 사용하도록 한다. 또한 1도 양수와 곱해졌을 때 손해가 되는 항목이다. (4*1<4+1) 묶지 않고 그냥 더하는 것이 크기 때문이다. 그래서 이 둘의 항목은 따로 셈을 해주도록 한다,

 양수와 음수로 분리를 하고 난 뒤에 음수는 오름차순, 양수는 내림차순으로 정렬해서 곱을 편하게 만들었다. 또한 이들의 개수가 홀수이면 예외처리를 따로 해줘야 하는 번거로움이 생기기 때문에 임의의 값인 1이나 0을 넣어주도록 했다. 

 이러한 사전작업이 끝난다면 두 값씩 묶은 뒤에 더해주도록 했다.

문제 링크:

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

문제:

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 시간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N=7인 경우에 다음과 같은 상담 일정표를 보자.

 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3,4,5,6 일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6,7이렝 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이 때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1<=Ti<=5,1<=Pi<=1,000)

출력:

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

풀이방법:

기간을 넘어가서 상담을 할 수는 없는 것이므로 뒤에서 부터 값을 업데이트 하며 오도록 하였다. i일의 최대 가능한 금액은 이전의 값을 그대로 가져오가나 몇일 지난 값을 더한 값이 되게 된다. 따라서 이 점화식에 따라서 계속해서 값을 구하다 보면 d[0]에 최대값이 담기게 된다.

문제링크:

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