CodeDrive

문제:

아래의 그림과 같이 높은 빌딩 사이를 따라 좁은 길이 나있다. 두 개의 사다리가 있는데 길이가 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을 보았다. 미르코는 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

문제:

길이가 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

문제:

2진수가 주어졌을 때, 8진수로 변환하는 프로그램을 작성하시오.

입력:

첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다.

출력:

첫째 줄에 주어진 수를 8진수로 변환하여 출력한다.

풀이방법:

2진수를 8진수로 바꾸는 수학적 방법은 2진수인 수 뒷부분부터 3개씩 끊어가면서 10진수 수로 변환을 하고 이를 이어붙이면 8진수 수가 된다.

즉 이 문제에서는 11001100이라는 예시가 있었을 때 뒤에서부터 3자리씩 끊으면 다음과 같다.

   11/001/100

따라서 이 수를 10진수 수로 변환하면 다음과 같다.

    3/1/4

답은 이 수들을 이어 붙인 314이다.

문제링크:

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

문제:

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 t(1<=t<=100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n(1<n<=100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1000000을 넘지 않는다.

출력:

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

풀이 방법:

조건에 주어진대로 수행만하면 되는 문제다. 주어진 n개의 수 중에 겹치지 않게 2개를 뽑고 그 값의 gcd를 구하고 배열에 더한 뒤에 sum을 하면 구할 수 있다.

문제 링크:

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

문제:

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 입력으로 주어지는 모든 수는 1,000,000보다 작거나 같으며, 공백으로 구분되어 있다.

출력:

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

풀이 방법:

  문제가 엄청 어려워 보이지만 "또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. " 이 문장이 함정이라는 것을 알면 어렵지 않게 된다. 실제로 예제 입력에 대해서 계속해서 부딪히게 만들어보았더니 개미가 먼 방향으로 걸어가서 떨어지는 것과 같은 값을 얻는다는 것을 알 수 있었다. (정확한 이유는 모르겠다.)

 따라서 가장 빠른 시간은 각자 개미들이 자신이 위치에서 막대가 짧은 쪽으로 이동하도록 하고, 가장 느린 시간은 개미들이 막대가 긴 쪽으로 이동하도록 한다면 값을 구할 수 있다. 배열에 넣어서 각 값을 구하도록 했더니 시간 초과가 발생해서 각 개미마다 비교해서 최솟값, 최댓값을 구하도록해서 시간을 줄이도록 했다.

문제 링크:

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

문제:

양의 정수 N이 주어졌을 때, 이 수를 소인수분해 한 결과를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 수가 주어진다. 각 테스트 케이스마다 양의 정수 N (2<=N<=100,000)이 주어진다.

출력:

각 테스트 케이스마다 각 인수와 그 인수가 곱해진 횟수를 한 줄씩 출력한다. 출력 순서는 인수가 증가하는 순으로 한다.

풀이 방법:

소인수분해는 말 그대로 소수로만 분해가 된다. 따라서 2부터 시작해서 n이 1이 될 때까지 소수로 나눠주면 된다. 소수인지 따로 판별이 필요하지 않다.(이전에서 이미 다 나눠버렸기 때문에) 따라서 각 count별로 answer를 계산하고 더 이상 나눠주지 못한다면 초기화를 하고 다음으로 넘어가면 된다.

문제 링크:

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

문제:

 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 데이터, ....,

 10번 데이터틑 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1<=a<100, 1<=b<1,000,000)

출력:

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

풀이 방법:

 a^b 꼴, 즉 제곱수 형태로 주어지기 때문에 일정한 규칙이 있게 된다. 계속 곱하다 보면 일의 자리가 반복됨을 알 수 있다.

1 -> 1 -> ...

2 -> 4 -> 8 -> 6 -> 2 -> ...

3 -> 9 -> 7-> 1 -> 3 ->...

4 -> 6 -> 4 -> ...

5 -> 5 -> ....

6 -> 6 -> ...

7 -> 9 -> 3 -> 1 -> 7 -> ....

8 -> 4 -> 2 -> 6 -> 8 -> ....

9 -> 1 -> 9 -> ....

10 -> 10 -> ... (원래는 0이겠지만 문제상에서는 10이다.)

따라서 a에 맞는 규칙 배열을 만들어 준 뒤에 b에 맞는 인덱스를 찾아 반환해주면 된다.

문제 링크:

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

문제:

입력:

출력:

풀이 방법:

 이와 같은 방법으로 5를 구한다음에 nCm =n! / (m! * (n-m)!) 이므로 이에 맞춰서 2의 갯수와 5의 갯수를 구한 뒤에 더 작은 값이 0의 갯수가 될 것이다.

문제:

입력:

출력:

풀이 방법: