문제 6064번: 카잉 달력 문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있� www.acmicpc.net 문제 풀이 첫 번째 해의 범위가 M, 두 번째 해의 범위가 N이고 현재 년도가 각각 x, y로 주어질 때 몇 번째 해인지 찾는 문제이다. 또한 N, M을 통해 세상의 종말이 도래하는 마지막 해를 구하여야 하는데 이는 N, M의 최소 공배수이다. 예시와 같이 M, N, x, y은 10, 12, 3, 9의 경우 다음과 같이 해당 연도를 구할 수 있다. x y 3 3 % 12 = 3 13 13 % 12 = 1 23 23 % 12 = 11 33 33 % 12 = 9 ..
문제 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타�� www.acmicpc.net 문제 풀이 지구, 태양, 달의 수 범위는 각각 15, 28, 19로 다르다. 그러면 지구, 태양, 달의 수가 주어졌을 때 이를 통해 년도를 구하는 방법은 간단하다. 현재 연도 - 지구의 수, 현재 연도 - 태양의 수, 현재 연도 달의 수가 15, 28, 19로 각각 나누었을 때 모두 0이 되면 입력 값에 올바른 연도를 구할 수 있다. 코드 from sys import stdin if __name__ == '__main__': e, s, m = map(int,..
문제 1748번: 수 이어 쓰기 1 첫째 줄에 N(1≤N≤100,000,000)이 주어진다. www.acmicpc.net 문제 풀이 브루트 포스로 풀면 시간 초과로 풀지 못한다. 그렇다면 어떻게 효율적으로 구할 수 있을까? 다음과 같은 경우를 생각해보면 쉽게 구할 수 있다. 자릿수는 몇 자릿수 인지를 의미한다. 예를 들어 1 ~ 9는 한 자릿수이다. 1 ~ 9 : 9개 * 자릿수 10 ~ 99 : 90개 * 자릿수 100 ~ 999 : 900개 * 자릿수 즉, 120의 경우 9 + 180 + ? 가 된다. 그럼 100과 120의 사이의 수들도 계산할 수 있다. (120 - 100 + 1) * 자릿수가 된다. 100과 120 사이의 값들 계산에서 +1을 해주는 것은 100도 포함되기 때문이다. 이와 같이 ..
문제 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 이전에 풀었던 1912 연속합에서 하나의 숫자를 뺄 수 있는 조건이 추가된 문제이다. 따라서 문제 풀이는 다음과 같이 접근할 수 있다. 아무것도 빼지 않는 연속합을 메모 이제이 션 한다. 구해진 연속합에서 중간에 수를 제거한 경우에 대한 값을 메모이제이션 한다. 1번의 경우는 연속합 문제에서 다루었다. 그럼 2번의 경우는 어떤식으로 찾을 수 있을까? 조금만 생각해보면 쉽게 답을 찾을 수 있다. 예를 들어 4개의 값이 있다면 OOXO와 같이 2번 인덱스..
