복습노트 복습노트

문제 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..

C++ 에서 사용할 수 있는 STL중 하나인 map입니다. 먼저 map을 사용하기 위해서는 위와 같이 헤더파일을 입력해줍니다. mapmap 이런식의 선언으로 사용가능합니다. map은 pair 형태로 data가 저장되며 로 이루어 집니다. map은 key의 중복값을 허용하지 않으며, 저장될 때는 key를 기준으로 자동적으로 오름차순으로 저장됩니다. 저장되는 형태는 red-black tree형태로 저장됩니다. 따라서 삽입이나 삭제를 할 때 시간복잡도가 O(log n)을 보장합니다. 1) 선언 key의 data type과 value의 data type을 결정할 수 있습니다. mapm1; mapm2; mapm3; mapm4; 2) 삽입 mapmap1; map1.insert({ 1,"kang" });//key가 ..

문제 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이 모자라면 땅을 채울 수 없습니다.) 처음에 이 문제를 접했을 때는 어떻게 진행해야 될지 감을 잡지 못해 구글에 찾아보았습니다. 문제의 접..

문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1 ~ n 으로 이루어진 수열이 주어지면 1부터 n 까지 차례대로 스택에 넣어 push와 pop을 통해 주어진 수열을 만들 수 있는지 확인하는 문제 입니다. 주어진 수열을 만들 수 있으면 push할 때마다 '+'를 출력하고 pop할 때 마다 '-'를 출력합니다. 만약 주어진 수열을 만들 수 없으면 NO를 출력하고 종료합니다. 정상적으로 주어진 수열을 만들 수 있으면 구현하는데..