접근법 문제를 단순화하는게 생각보다 어려웠다. 그러나 목적은 조건에 맞도록 가장 최소한의 장치를 작동시키면 된다. 따라서 주어진 조건을 만족시키는 수열을 하나씩 만들어봤다. ( 아래 그림 참조! ) 어차피 입력값으로 받는 시작점과 끝점 사이의 거리 (Distance) 가 핵심이기 때문에 이 거리 값에 맞게 답을 구하면 된다. 하나씩 나열해보면, 찾을 수 있는 규칙이 있다. 제곱수 시점에서 횟수가 1 증가한다. 제곱수를 N이라고 한다면, N에서 양의 제곱근 (이하 n) 을 뺀 시점에서 또 횟수가 증가한다. 여기서, N(제곱수)의 바로 전 시점까지의 횟수는 2n - 1 N - n 의 직전 시점에서의 횟수는 2n - 2 Distance 의 값을 알고 있다면 위 규칙을 따라서 손쉽게 문제를 풀 수 있다. Dis..
접근법 보통 이런 형태의 문제는 우선 나열해보면 규칙이 보이는 경우가 많다. 우선, 문제를 살펴보면 규칙은 정해져 있고 몇 층의 몇 호에 몇 명이 사는지 확인하는 문제이다. 아파트는 조건에 적혀있듯 0층부터 시작하고 각 층은 0호부터 14호까지 있으며, 규칙에 따라 한번 나열해보면, 2층 1 4 10 20 35 ... 1층 1 3 6 10 15 ... 0층 1 2 3 4 5 ... 0층을 제외하고 규칙을 보면 2층 2호는 [ 2층 1호 + 1층 2호 ] 의 값과 같다. 또한, 1층 4호는 [ 1층 3호 + 0층 4호 ] 의 값과 같은 것을 확인할 수 있다. 구하고자 하는 층의 거주자는 위치적으로 왼쪽과 아래쪽에 사는 거주자를 합한 값과 같고 이를 일반화하면 A층 B호 = (A층 B-1호) + (A-1층 ..
접근법 문제가 길어서 어려워 보이지만 그렇게 어렵지 않게 풀 수 있다. 핵심은 H(높이) 와 W(호수)에서 N번째 손님은 몇 번째 W에 속하는가이다. 즉, N을 H로 나누면 어느 정도 W에 위치하는지에 대한 정보를 구할 수 있다! 아래 표를 예시로 보자. 높이 4에 너비가 5인 호텔이라고 가정하자. 여기서 15번째 손님에 대해 방 배정을 할 경우 15를 높이인 4로 나누어 보자. 몫이 3에 나머지가 3이나온다. 즉, 나머지가 있을 때는 (몫 + 1) 의 W에 위치한다는 것을 알 수 있고, 그 높이는 나머지만큼 올라간다. (3층의 4호) 두번째로 12번째 손님에 대해서 방배정을 해보면 같은 방법으로 몫이 3에 나머지는 없다. 이 경우에는 몫에 해당하는 W의 가장 꼭대기층 (H값) 에 있음을 알 수 있다. ..
접근법 달팽이가 하루에 올라갈 수 있는 높이는 A - B 미터이다. 하지만 중요한 점은, A높이만큼 올라간 뒤에 정상이라면 더 이상 미끄러지지 않는다는 것이다. 그렇기 때문에 하루에 올라갈 수 있는 높이를 단순하게 (A - B) 로 일반화할 수 없다. 따라서 이 부분만 조금 생각해보면 어떻게 접근해야할지 감을 잡을 수 있다. V - A = 마지막 날 전까지 올라가야 할 높이이다. ( H로 명명 ) H / (A - B) 의 몫 = 마지막 전날까지 올라가기까지 걸리는 날짜 의 나머지 = 마지막 전날까지 올라간 뒤 남은 높이 (이 수치는 A보다는 크고 A-B보다는 작을 것이다.) 나머지가 0 일 때 정확히 ( A - B ) 의 값으로 나누어 떨어졌다는 의미는 곧 마지막 날에 A높이만큼만 더 올라가면 된다는 뜻..
#1712 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만 원이 들며, 열 대 생산하는 데는 총 1,700만 원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다. A..
#1152 단어의 개수 영어 대소문자와 띄어쓰기만으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다. 입력 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. 입출력 예제 입력 출력 The Curious Case of Benjamin Button 6 Mazatneunde Wae Teullyeoyo 3 Teullinika Teullyeotzi 2 풀이 sentence = input().strip..