지구정복

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net -문제해설 처음에 팩토리얼 재귀함수로 하려니깐 값이 너무 커져서 틀렸다고 나왔다. 뭔가 굳이 n!을 다 구하지 않고 0의 개수만 알 수 있는 방법이 없나 생각하다가 그냥 노가다로 인터넷에 팩토리얼 계산기를 이용해서 규칙이 있는 지 확인했는데 신기하게도 규칙이 있었다. ㅎ 1~4 : 0 5~9 : 1 10~14 : 2 15~19 : 3 20~24 : 4 ㅡㅡㅡㅡㅡ25의 배수일 때는 + 2 25~29 : 6 . . . 45~49 : 10 ㅡㅡㅡㅡㅡ 50~54 : 12 . . . 70~7..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net -문제해설 처음에 해시맵 두 개로 풀었는데 다른 분들 풀이를 보니 그냥 배열과 맵을 가지고도 충분히 풀 수 있는 문제였다. 먼저 필요한 거는 book1이란 배열과 book2란 해시맵이다. book1의 인덱스는 입력되는 순서 1부터 26이 되고 각 인덱스의 값은 포켓몬 이름이 된다. book2 해시맵에서는 book1과 반대로 키가 포켓몬 이름이 되고 값이 입력되는 순서가..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net -문제해설 처음에 점화식을 잘못 세워서 약간 고생을 했다; 주어진 수를 제곱합으로 만들기 위해 필요한 최소의 제곱합의 개수를 구하는 문제이다. 제곱합의 개수가 담기는 배열을 dp라고 하자. dp[1] = 1이다. 왜냐하면 1을 만들 수 있는 제곱합의 수는 1의 제곱밖에 없기 때문에 개수는 1개이다. 2를 만들기 위한 최소의 제곱합의 개수는 i - j*j = 2 ..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net -문제해설 처음에 ArrayList에 값을 넣어서 풀었더니 시간초과가 나왔다... 그 다음에는 문제에서 집어넣은 값을 다시 출력하라는 말은 없기 때문에 add되는 값을 배열의 인덱스로 설정해서 풀어보려고 했는데 비트마스크를 이용하면 효율적으로 풀 수 있다는 글을 보았다. 결국 비트마스크를 공부한 뒤 문제를 풀 수 있었다. 비트마스크에 대해 공부한 내용을 간략히 정리하면 이 문제의 경우 입력받은 값을 그대로 출력하라는 조건은 없고 c..