복습노트 복습노트

문제 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net m과 n이 주어지고 x와 y가 주어지면 가 몇번째로 이루어지는지 구하는 문제입니다. 만약 가 안되면 -1을 출력하면 됩니다. 부터 시작하며 x' n을 넘어가면 다시 x'가 1로 되고 y도 마찬가지 입니다. 예를 들어 m과 n이 10, 12 라면 부터 시작해 까지 가고 은 x'가 m을 넘어가 되므로 다음에는 이 됩니다. 마찬가지로 가 되고 다음 순서는 이 되어야 하지만 y'가 n을 넘어가게 되므로 가 됩니다. 는 60번째 에서 마지막이 되고 끝이 납니다. 단순히..

문제 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 숫자와 연산자가 포함된 식이 주어지면 임의의 괄호를 쳐서 가장 작은수를 출력하면 됩니다. 예를 들어 55 - 50 + 40 이라는 식이 주어지면 55 -(50 + 40) = -35 이렇게 최소의 값을 출력하게 하면 됩니다. 처음에는 괄호를 처음부터 치면서 brute force문제 인지 알았지만 brute force로 구현이 어려워 힌트를 찾아봤습니다. 100 - 10 + 50 -10 + 100 다음과 같은 식을 최소로 만들려면 100 -(10 + 50..

문제 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net n이 주어지면 n의 제곱수로 이루어진 개수를 구하는 문제입니다. 예를 들어 n이 10이면 10 = 3^2 + 1^2 총 2개가 됩니다. 규칙을 찾아보면 제곱수 (4, 9, 16, 25, ,,,,,) 들은 항상 개수가 1입니다. 즉 제곱수가 최소로 이루어져야 하므로 n 이하의 제곱수를 중심으로 살펴봐야합니다. 예를 들어 n이 12 라면 n이하의 제곱수는 1, 4, 9가 있습니다. 점화식을 세워보면 dp[12] = dp[1] ..

문제 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 옷의 종류가 n개 주어지면 종류가 겹치지 않는 선에서 아무것도 입지 않은 상태를 제외한 경우의 수를 구하는 문제 입니다. 예를 들어 n = 3이고 옷의 종류가 다음과 같이 주어지면 hat headgear sunglasses eyewear turban headgear (hat), (turban), (sunglasses), (hat,sunglasses), (turban..

문제 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문자열을 n개 입력하면 m개의 문자열 또는 숫자를 입력할 수 있습니다. 만약 문자를 입력하면 몇번째로 입력이 들어왔는지 출력하고 숫자를 입력하면 숫자에 해당하는 순서에 들어온 문자열을 출력하면 됩니다. 숫자를 입력하면 단순히 pair 형으로 string과 순서를 쌍으로 입력받아 바로 출력해주면 됩니다. 하지만 문자를 입력하면 수많이 들어온 문자열을 다 찾아가면서 찾아야 합니다. 그렇게 되면 시간이 많이 걸립니다. 총 2가지 방법..

문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 집합 S에 다음과 같은 명령어를 m (m HTML 삽입 미리보기할 수 없는 소스

문제 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net n이 주어지면 n!의 뒤에서 부터 0이 아닌 수가 나올 때까지 0의 개수를 세는 문제입니다. 우리가 숫자 뒤에 0이 붙게 될려면 숫자에서 10을 곱해주면 됩니다. 즉 숫자에서 10이 몇번 곱해있는지 확인하면 뒤에 0이 몇번 붙었는지 알 수 있습니다. 10을 소인수분해 하면 2 * 5가 나옵니다. 결국 1부터 n까지 2와 5의 약수의 개수를 세고 작은 수를 출력하면 됩니다. 모든 수는 5의 약수가 훨씬 적으므로 우리는 1부터 n까지 돌아가면서 5의 약수를 구하면 됩니다. 만약 i가 5의 거듭제곱 꼴(ex : 25, 125 등등) 이면 단순히 (..

문제 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 다음과 같은 땅을 평평하게 만드는데 걸리는 최소 시간과 높이를 구하는 문제입니다. 땅을 평평하게 만드는 방법은 2가지가 있습니다. 1. 땅을 파기(시간이 2초가 걸립니다. 대신에 주어진 block이 1개 늘어납니다.) 2. 땅을 채우기(시간이 1초 걸립니다. 대신에 주어진 block이 1개 줄어듭니다. 주어진 block이 모자라면 땅을 채울 수 없습니다.) 처음에 이 문제를 접했을 때는 어떻게 진행해야 될지 감을 잡지 못해 구글에 찾아보았습니다. 문제의 접..