지구정복

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net -문제해설 자바로는 BFS를 이용했고, 파이썬에서는 DFS를 이용했다. -자바 package bfs_dfs; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.String..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net -문제해설 전형적인 BFS문제이다. 그래프 이동을 위해서 dx, dy 배열을 지정하고 반복문을 돌면서 좌표를 이동시킨다. 이때 중요한 점은 이동횟수를 큐에 같이 집어넣어줘야한다. 이를 위해서 Point 사용자 클래스를 정의하고 필드값은 x, y, ans 이다. ans는 이동횟수를 나타내는 변수이다. 자세한 내용은 아래 코드 참고 -자바 package bfs_dfs; import java.io.Buf..

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