비행기들의 도착시간, 출발시간이 주어져 있고. 레인은 하나밖에 없습니다. 비행기 주차장은 항상 LIFO(Last In First Out)입니다. 제 시간에 맞춰서 떠날 수 있는 비행기는 최대 몇 대인가?
문제를 약간 단순화 시켜서 접근해보겠습니다. 입력으로 주어진 도착시간/출발시간이 모두 다르고, 1 ~ 2n 으로 주어진다고 가정합시다.
"table[i][j]를 i 시간부터 j 시간까지 사용할 수 있을 때, 최대 몇 대의 비행기를 떠나 보낼 수 있는가?"로 정의한다면, 이 문제는 DP로 접근 가능합니다. 모든 비행기에 대하여 table[도착시간][출발시간] = 1 로 초기화 하고, table[i][j] = { k = [i, j) }table[i][k] + table[k + 1][j] 로 해결할 수 있지요.
그럼 이제 문제는 똑같은 시간에 여러번 사건이 발생할 수 있는 것이 됩니다. 아래와 같은 데이터가 문제가 되겠지요.
A(1, 5), B(2, 5), C(5, 8), D(5, 9)
5라는 시간에 A, B, C, D 모두 공항을 사용해야 하는 상황이지요. 순서를 잘 배치하면 모두 공항을 이용할 수 있을 것 같습니다. 시간 5에 출발할 수 있는 비행기들을 다 떠내보낸 다음, 도착하는 비행기들을 받아야 순서가 맞을 듯 합니다. 만약 A, B가 출발하기 전에 C가 도착한다면 A나 B는 제 시간에 출발할 수 없으니까요. 즉 A, B는 C, D보다 항상 먼저 떠나야 합니다.
A와 B 사이의 우선순위를 생각해보도록 합시다. A는 B보다 공항에 먼저 도착했습니다. 따라서 출발하는 순서는 B가 A보다 먼저가 되겠네요. 따라서 '같은 시간에 출발하는 비행기들은 늦게 도착한 비행기가 먼저 떠남'이 되겠습니다. C와 D 사이의 우선순위는 어떻게 될까요? 도착시간이 같다면, 늦게 출발하는 녀석을 먼저 받아야 우선순위가 꼬이지 않을 듯 하네요. '같은 시간에 도착하는 비행기들은 늦게 도착한 비행기가 먼저 떠남' 이 됩니다.
이제 같은 시간이 들어왔을때의 우선순위를 정할 수 있게 되었으니 해법 초반에 설명했던 DP를 활용함으로써 A번 문제를 해결할 수 있습니다. :D
B. Omega Coding
n이 주어졌을 때, Omega Code를 구하는 문제입니다.
2진수 변환을 할 수 있고, 간단한 string 연산을 할 수 있다면 쉽게 풀 수 있는 문제입니다
C. In-circles Again
삼각형 ABC에 내접하는 반지름 r인 원이 있다. 또한 이 원과 삼각형 ABC의 두 변에 접하는 반지름 r1, r2, r3인 원이 있다. r, r1, r2, r3가 입력으로 주어질 때 삼각형 ABC의 넓이를 구하는 프로그램을 작성하시오.
삼각형의 각 변의 길이를 구한 다음, S = (a + b + c) / 2 일때, area = sqrt( S * (S - a) * (S - b) * (S - c) )를 이용하면 됩니다. 수학이네요.
D. Rating Hazard
1~5점 까지 Review 점수를 줄 수 있는 시스템이 있습니다. (반올림된) 평균 점수가 입력으로 주어질 때, 이 점수를 얻을 수 있는 최소 인원을 구하시오. 예를 들어 3.67이 입력으로 주어진다면, 3명의 Customer가 3점, 4점, 4점을 투표했을 때. (3+4+4)/3 = 3.66666 ~= 3.67 가 되므로, 최소 인원은 3이 됩니다.
대회 끝나고 푼 사람들끼리 토론을 했었는데, 다양한 풀이가 나왔습니다 'ㅅ' 제 방법을 간단히 설명하자면
입력으로 주어진 수의 소수부만을 취합니다. 정수부는 어쨌든 상관 없으니까요. 1.15 -> 0.15
이 수를 분수로 바꿔줍니다. 0.15 -> 15/100
우리가 구하고자 하는 분수가 가능한 범위를 구해봅시다. 145 / 1000 이상 155 / 1000 미만이 되겠네요.
145 / 1000 <= A / B < 155 / 1000 일 때, 우리가 구할 것은 이 조건을 만족하는 A/B 중 B를 최소화 하는 것이 됩니다.
위의 역수를 취해봅니다. 1000 / 155 < B / A <= 1000 / 145 가 됩니다. 여전히 B를 minimize하면 됩니다.
모든 항에 A를 곱하면, 1000A / 155 < B <= 1000A / 145가 됩니다. A를 1씩 증가시키면서 정수 B가 존재하는지를 구하면 되겠네요.
그런데 위에서 말한 방식으로만 코딩하면 TLE를 피할 수 없습니다. 그래서 저는 나누기 대신 분수를 사용했어요. 1000A / 155 => P + Q/155 꼴로 나타낼 수 있으니까요. P, Q 모두 정수가 되지요. 그리고 A를 1 증가시킨다는 뜻은 이전까지의 결과에서 1000 / 155 = 6 + 70/155 를 더하는 것과 같기 때문에 P, Q 값에 더하기만을 가지고도 구할 수 있습니다. Q가 155보다 크다면 P를 1 증가, Q를 155만큼 감소시켜주면 되고요. 기타 다른 풀이는 제가 이해를 못한 관계로... 다른 방법으로 풀어주신 분들이(kcm1700 or legend12) 써 주실겁니다 'ㅅ'
E. Relational Operators
'lvalue Operator rvalue' 형식의 입력이 주어질 때, 이 값이 true인지 false인지 출력하는 프로그램을 작성하시오. Operator에는 >, >=, <, <=, ==, != 가 있다.
문자열 입력만 할 수 있다면 누구나 풀 수 있는 문제라고 생각합니다.
F. Your Ways
(0, 0) 부터 (w, h)까지 격자모양으로 도로가 있고, K개의 쿼리가 입력으로 주어집니다. 각 쿼리는 지나갈 수 없는 도로의 수 Qi와 도로의 정보(A,B)-(C,D)를 알려줍니다. w, h는 1000 이하의 정수이고, K는 10,000 이하의 정수입니다. 도로의 길이는 항상 1입니다.
(0, 0)에서 (w, h)까지 갈 수 있는 경우의 수를 구해봅시다. 'ㅅ'
K가 작다면 O(Kwh)의 복잡도를 가지는 DP로 해결할 수 있습니다만, K * w * h값이 너무 크네요. 이 문제를 풀기 위한 Keyword는 '포함배제의 원리' 입니다.
G. Hexagonal Sticks
벌집모양의 보드가 주어져 있습니다. (문제를 참조하세요) 그리고 S개의 막대기가 있습니다. 이 막대기를 이동하거나 제거하여 정육각형을 만들고 싶습니다. 단 정육각형을 만들고 남는 막대기가 있어서는 안 됩니다. 이동하거나 제거하는 데는 모두 1의 cost가 사용됩니다. 입력으로 주어지는 막대기의 좌표는 [-4, 4] 범위 안이며, 정육각형을 만들 수 없는 경우에는 impossible을 출력합니다.
입력으로 주어진 막대기를 임의의 위치로 이동시킨다고 할 때의 최단거리를 미리 구해둡니다. 막대기는 최대 8개이고, 상태공간이 그다지 크지 않기 때문이지요.
H. Buy Your House
(0, 0) 부터 (w, h)까지 격자모양의 땅이 있습니다. 여기에는 n개의 집이 있고, 모든 집은 x-y 축에 평행한 직사각형 모양입니다. 당신은 (x1, y1) - (x2, y2)의 땅을 사려고 하는데, 당신이 구입하고자 하는 땅에는 집이 반드시 1채만 있어야 합니다. 돈이 없어서 2채 이상 있으면 못삽니다. 당신의 땅에 포함된 집은 쪼개져서는 안되며, 당신이 산 땅에 다른 집의 일부분이 포함되어도 안됩니다. 당신이 살 수 있는 땅의 경우의 수를 출력하세요. 답이 크기 때문에 1,000,000,007로 나눈 나머지를 출력하면 됩니다.
(별로 화려하진 않지만) 그림을 하나 그려보았습니다. 파란색 집을 이번에 반드시 포함할 집이라고 가정해 봅시다. 그러면 "녹색"으로 칠한 부분이 왼쪽 아래 점, 혹은 오른쪽 위 점이 위치할 수 있는 범위가 됩니다. 이는 Convex 형태가 됩니다.
임의의 점 A를 왼쪽 아래점으로 고정시켰다고 할 때, 파란색 집을 포함하는 경우의 수를 모두 구해보면 오른쪽 위의 사선으로 칠한 부분의 넓이가 됩니다. 이 점 A를 왼쪽의 녹색 부분에 대해서 모두 매칭하면 답을 구할 수 있긴 하지요. (다만 엄청 느릴지도...)
속도 개선을 위해, 전체 보드를 조각내서 접근합니다. plane-sweeping 이라고 하던가요 'ㅅ' 그러면 좌표의 범위가 크더라도, 실제 조각의 수는 많이 줄어들게 됩니다. 이를 통해 속도를 개선하면 제한시간 내에 구할 수 있습니다.
저는 이 문제를 푸는데 n시간쯤 고민하고 2시간 코딩했습니다 :( 이상한데서 오차가 나서... 집에 도착하는대로 코드를 첨부하겠습니다 ;ㅁ;
I. Synnerg Lifeform
과학자들이 골방에서 synnerg라는 작은 생명체를 발견했습니다. 새로 태어난 synnerg는 모두 1인 같은 수명을 가지고 있으며, 두 synnerg가 결합하게 되면 새로운 synnerg가 만들어지는데, 이 synnerg의 수명은 (Amplification Factor) * (Source #1의 수명 + Source #2의 수명) 이 됩니다. 주어진 synnerg의 sequence가 최대한 오래 생존하는 경우의 수명과, 경우의 수를 출력하시오.
A번과 비슷한 류의 DP입니다. table[i][j] = 'i부터 j까지의 synnerg를 사용했을 때의 최대 수명 및 결과 synnerg' 로 정의해 두면 DP로 접근할 수 있게 됩니다. map을 적절하게 쓰면 string type의 synnerg를 정수화해서 저장할 수 있지요.
J. Nowhere Money
customer들은 거스름돈을 받을 때, 아래의 두 가지 조건을 만족하기를 바라고 있습니다.
number of slot은 적을 수록 좋다.
i번째 슬롯과 i+1번째 슬롯의 거스름돈을 동시에 받는것은 원하지 않는다.
당신은 위와 같은 조건을 만족하는 슬롯을 만들었습니다. 거스름돈 n이 주어졌을 때, 슬롯 번호. 각 동전의 가치를 출력하세요. 거스름돈 n은 5,000,000,000,000,000,000 이하입니다.
위의 두 조건을 만족하는 슬롯은 Fibonacci Number가 됩니다. (어떻게 저 조건이 피보나치가 되느냐! 라고 질문하신다면 참으로 대답하기 난감하네요...) 피보나치의 규칙성[?] 때문이라고 말해야 할까요...
astein
안녕하세요. astein입니다
이걸 써야 1주1셋 하나 더 열어준다는 압박이 들어와서... 에디토리얼 시작합니다.
문제를 어느정도 알고 있다는 가정하에 에디토리얼을 쓰고 있습니다. 'ㅅ' (문제는 간단하게 썼습니다..)
그리고 어느정도 Trivial하다고 생각하는 문제에 대해서는 Comment 정도만 달아두었으니 질문이 있으면 댓글로 남겨주세요.
문제는 http://thelibe.pe.kr/contest/ 에 있습니다.
A. Airplane Parking
비행기들의 도착시간, 출발시간이 주어져 있고. 레인은 하나밖에 없습니다. 비행기 주차장은 항상 LIFO(Last In First Out)입니다. 제 시간에 맞춰서 떠날 수 있는 비행기는 최대 몇 대인가?
문제를 약간 단순화 시켜서 접근해보겠습니다. 입력으로 주어진 도착시간/출발시간이 모두 다르고, 1 ~ 2n 으로 주어진다고 가정합시다.
"table[i][j]를 i 시간부터 j 시간까지 사용할 수 있을 때, 최대 몇 대의 비행기를 떠나 보낼 수 있는가?"로 정의한다면, 이 문제는 DP로 접근 가능합니다. 모든 비행기에 대하여 table[도착시간][출발시간] = 1 로 초기화 하고, table[i][j] = { k = [i, j) }table[i][k] + table[k + 1][j] 로 해결할 수 있지요.
그럼 이제 문제는 똑같은 시간에 여러번 사건이 발생할 수 있는 것이 됩니다. 아래와 같은 데이터가 문제가 되겠지요.
A(1, 5), B(2, 5), C(5, 8), D(5, 9)
5라는 시간에 A, B, C, D 모두 공항을 사용해야 하는 상황이지요. 순서를 잘 배치하면 모두 공항을 이용할 수 있을 것 같습니다. 시간 5에 출발할 수 있는 비행기들을 다 떠내보낸 다음, 도착하는 비행기들을 받아야 순서가 맞을 듯 합니다. 만약 A, B가 출발하기 전에 C가 도착한다면 A나 B는 제 시간에 출발할 수 없으니까요. 즉 A, B는 C, D보다 항상 먼저 떠나야 합니다.
A와 B 사이의 우선순위를 생각해보도록 합시다. A는 B보다 공항에 먼저 도착했습니다. 따라서 출발하는 순서는 B가 A보다 먼저가 되겠네요. 따라서 '같은 시간에 출발하는 비행기들은 늦게 도착한 비행기가 먼저 떠남'이 되겠습니다. C와 D 사이의 우선순위는 어떻게 될까요? 도착시간이 같다면, 늦게 출발하는 녀석을 먼저 받아야 우선순위가 꼬이지 않을 듯 하네요. '같은 시간에 도착하는 비행기들은 늦게 도착한 비행기가 먼저 떠남' 이 됩니다.
이제 같은 시간이 들어왔을때의 우선순위를 정할 수 있게 되었으니 해법 초반에 설명했던 DP를 활용함으로써 A번 문제를 해결할 수 있습니다. :D
B. Omega Coding
n이 주어졌을 때, Omega Code를 구하는 문제입니다.
2진수 변환을 할 수 있고, 간단한 string 연산을 할 수 있다면 쉽게 풀 수 있는 문제입니다
C. In-circles Again
삼각형 ABC에 내접하는 반지름 r인 원이 있다. 또한 이 원과 삼각형 ABC의 두 변에 접하는 반지름 r1, r2, r3인 원이 있다. r, r1, r2, r3가 입력으로 주어질 때 삼각형 ABC의 넓이를 구하는 프로그램을 작성하시오.
삼각형의 각 변의 길이를 구한 다음, S = (a + b + c) / 2 일때, area = sqrt( S * (S - a) * (S - b) * (S - c) )를 이용하면 됩니다. 수학이네요.
D. Rating Hazard
1~5점 까지 Review 점수를 줄 수 있는 시스템이 있습니다. (반올림된) 평균 점수가 입력으로 주어질 때, 이 점수를 얻을 수 있는 최소 인원을 구하시오. 예를 들어 3.67이 입력으로 주어진다면, 3명의 Customer가 3점, 4점, 4점을 투표했을 때. (3+4+4)/3 = 3.66666 ~= 3.67 가 되므로, 최소 인원은 3이 됩니다.
대회 끝나고 푼 사람들끼리 토론을 했었는데, 다양한 풀이가 나왔습니다 'ㅅ' 제 방법을 간단히 설명하자면
모든 항에 A를 곱하면, 1000A / 155 < B <= 1000A / 145가 됩니다. A를 1씩 증가시키면서 정수 B가 존재하는지를 구하면 되겠네요.
그런데 위에서 말한 방식으로만 코딩하면 TLE를 피할 수 없습니다. 그래서 저는 나누기 대신 분수를 사용했어요. 1000A / 155 => P + Q/155 꼴로 나타낼 수 있으니까요. P, Q 모두 정수가 되지요. 그리고 A를 1 증가시킨다는 뜻은 이전까지의 결과에서 1000 / 155 = 6 + 70/155 를 더하는 것과 같기 때문에 P, Q 값에 더하기만을 가지고도 구할 수 있습니다. Q가 155보다 크다면 P를 1 증가, Q를 155만큼 감소시켜주면 되고요. 기타 다른 풀이는 제가 이해를 못한 관계로... 다른 방법으로 풀어주신 분들이(kcm1700 or legend12) 써 주실겁니다 'ㅅ'
E. Relational Operators
'lvalue Operator rvalue' 형식의 입력이 주어질 때, 이 값이 true인지 false인지 출력하는 프로그램을 작성하시오. Operator에는 >, >=, <, <=, ==, != 가 있다.
문자열 입력만 할 수 있다면 누구나 풀 수 있는 문제라고 생각합니다.
F. Your Ways
(0, 0) 부터 (w, h)까지 격자모양으로 도로가 있고, K개의 쿼리가 입력으로 주어집니다. 각 쿼리는 지나갈 수 없는 도로의 수 Qi와 도로의 정보(A,B)-(C,D)를 알려줍니다. w, h는 1000 이하의 정수이고, K는 10,000 이하의 정수입니다. 도로의 길이는 항상 1입니다.
(0, 0)에서 (w, h)까지 갈 수 있는 경우의 수를 구해봅시다. 'ㅅ'
K가 작다면 O(Kwh)의 복잡도를 가지는 DP로 해결할 수 있습니다만, K * w * h값이 너무 크네요. 이 문제를 풀기 위한 Keyword는 '포함배제의 원리' 입니다.
G. Hexagonal Sticks
벌집모양의 보드가 주어져 있습니다. (문제를 참조하세요) 그리고 S개의 막대기가 있습니다. 이 막대기를 이동하거나 제거하여 정육각형을 만들고 싶습니다. 단 정육각형을 만들고 남는 막대기가 있어서는 안 됩니다. 이동하거나 제거하는 데는 모두 1의 cost가 사용됩니다. 입력으로 주어지는 막대기의 좌표는 [-4, 4] 범위 안이며, 정육각형을 만들 수 없는 경우에는 impossible을 출력합니다.
입력으로 주어진 막대기를 임의의 위치로 이동시킨다고 할 때의 최단거리를 미리 구해둡니다. 막대기는 최대 8개이고, 상태공간이 그다지 크지 않기 때문이지요.
H. Buy Your House
(0, 0) 부터 (w, h)까지 격자모양의 땅이 있습니다. 여기에는 n개의 집이 있고, 모든 집은 x-y 축에 평행한 직사각형 모양입니다. 당신은 (x1, y1) - (x2, y2)의 땅을 사려고 하는데, 당신이 구입하고자 하는 땅에는 집이 반드시 1채만 있어야 합니다. 돈이 없어서 2채 이상 있으면 못삽니다. 당신의 땅에 포함된 집은 쪼개져서는 안되며, 당신이 산 땅에 다른 집의 일부분이 포함되어도 안됩니다. 당신이 살 수 있는 땅의 경우의 수를 출력하세요. 답이 크기 때문에 1,000,000,007로 나눈 나머지를 출력하면 됩니다.
(별로 화려하진 않지만) 그림을 하나 그려보았습니다. 파란색 집을 이번에 반드시 포함할 집이라고 가정해 봅시다. 그러면 "녹색"으로 칠한 부분이 왼쪽 아래 점, 혹은 오른쪽 위 점이 위치할 수 있는 범위가 됩니다. 이는 Convex 형태가 됩니다.
임의의 점 A를 왼쪽 아래점으로 고정시켰다고 할 때, 파란색 집을 포함하는 경우의 수를 모두 구해보면 오른쪽 위의 사선으로 칠한 부분의 넓이가 됩니다. 이 점 A를 왼쪽의 녹색 부분에 대해서 모두 매칭하면 답을 구할 수 있긴 하지요. (다만 엄청 느릴지도...)
속도 개선을 위해, 전체 보드를 조각내서 접근합니다. plane-sweeping 이라고 하던가요 'ㅅ' 그러면 좌표의 범위가 크더라도, 실제 조각의 수는 많이 줄어들게 됩니다. 이를 통해 속도를 개선하면 제한시간 내에 구할 수 있습니다.
저는 이 문제를 푸는데 n시간쯤 고민하고 2시간 코딩했습니다 :( 이상한데서 오차가 나서... 집에 도착하는대로 코드를 첨부하겠습니다 ;ㅁ;
I. Synnerg Lifeform
과학자들이 골방에서 synnerg라는 작은 생명체를 발견했습니다. 새로 태어난 synnerg는 모두 1인 같은 수명을 가지고 있으며, 두 synnerg가 결합하게 되면 새로운 synnerg가 만들어지는데, 이 synnerg의 수명은 (Amplification Factor) * (Source #1의 수명 + Source #2의 수명) 이 됩니다. 주어진 synnerg의 sequence가 최대한 오래 생존하는 경우의 수명과, 경우의 수를 출력하시오.
A번과 비슷한 류의 DP입니다. table[i][j] = 'i부터 j까지의 synnerg를 사용했을 때의 최대 수명 및 결과 synnerg' 로 정의해 두면 DP로 접근할 수 있게 됩니다. map을 적절하게 쓰면 string type의 synnerg를 정수화해서 저장할 수 있지요.
J. Nowhere Money
customer들은 거스름돈을 받을 때, 아래의 두 가지 조건을 만족하기를 바라고 있습니다.
i번째 슬롯과 i+1번째 슬롯의 거스름돈을 동시에 받는것은 원하지 않는다.
당신은 위와 같은 조건을 만족하는 슬롯을 만들었습니다. 거스름돈 n이 주어졌을 때, 슬롯 번호. 각 동전의 가치를 출력하세요. 거스름돈 n은 5,000,000,000,000,000,000 이하입니다.
위의 두 조건을 만족하는 슬롯은 Fibonacci Number가 됩니다. (어떻게 저 조건이 피보나치가 되느냐! 라고 질문하신다면 참으로 대답하기 난감하네요...) 피보나치의 규칙성[?] 때문이라고 말해야 할까요...
K. Highway Patrol
아래에 Neon님이 쓰신 에디토리얼을 참조해주세요 :9
15년 전