지구정복

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net -문제해설 그냥 주어진 i와 j인덱스를 반복문으로 돌면서 구간 합을 구할 경우 시간초과가 나오게 된다. 따라서 애초에 데이터를 배열에 집어넣을 때 첫 번째 인덱스부터 삽입되는 인덱스까지의 누적 합을 구한 뒤 배열에 집어넣고 i부터 j까지의 구간합을 구하는 방법은 다음과 같다. arr[ j ] - arr[ i-1 ] 예를 들어서 배열 5 4 3 2 1 이 있을 때 2번 인덱스..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net -문제해설 돈을 인출하는데 오래 걸리는 사람이 앞쪽에 오게되면 뒤에 있는 사람은 그 만큼 더 많이 기다려야한다. 만일 적게 걸리는 사람이 앞에 오면 뒤에 있는 사람은 덜 기다리게 되므로 p배열을 오름차순으로 정렬한 뒤 각 사람이 기다린 시간인 tmp를 구하고 전체 기다리게 되는 시간이 sum에 tmp값을 더해주면 된다. -자바 package math; import java.io.BufferedReader; import java..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net -문제해설 기본적인 다이나믹 프로그래밍 문제이다. 바텀업방식으로 풀면 금방 풀 수 있다. 이때 dp 배열은 long타입으로 선언해야된다. 점화식은 다음과 같다. dp[n] = dp[n-3] + dp[n-2] (단, n이 1 또는 2일 때는 dp[1] = 1, dp[2] = 1 ) -자바 package ex; import java.io.BufferedReader; import java.io.IOExcep..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net -문제해설 옷의 종류만 중요하고 옷이 무엇인지는 중요하지 않다. HashMap을 이용해서 동일한 옷의 종류면 그냥 옷의 개수를 1씩 올리고 없으면 새로운 옷의 종류를 키로 삽입하고 값은 1로 설정한다. 그리고 아래 공식으로 출력값을 만든다. sum = (첫 번째 종류의 옷 개수 + 1) * (두 번째 종류..