목록지구정복과정 (466)
지구정복
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net -문제해설 문제는 듣도못한 사람과 보도못한 사람이 겹치는 사람의 수와 이름을 출력하는 것이다. 듣도못한 사람이 3 홍길동 김길동 박길동 보도못한 사람이 4 홍길동 박길동 이길동 정길동 이라고하면 이름은 사전순으로 출력해야 하므로 2 박길동 홍길동 이 된다. 이를 위해 처음에 해시맵 hs1에 ( 키: 이름, 값: 1 ) 로 듣도못한 사람들을 삽입한다. 그리고 arr ArrayList를 만들고 보도..
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 ..