지구정복

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net -문제해설 손으로 직접 다 써봤더니 점화식을 세울 수 있는 규칙을 찾을 수 있었다. 화질이 구려도 알아볼 수는 있으니 ㅎㅎ 맨 위 사진에서보면 일단 n이 1일 때 k이 증가함에 따라 나올 수 있는 개수도 1씩 증가한다. 그리고 k가 1일 때는 무조건 1이다. 나머지의 경우는 만약 ( 4, 3 )을 구한다고하면 ( 4, 2 ) + ( 3, 3 )을 더하면 나오는 것을 알 수 있다. 이를 코드화하면 아래와 같다. -자바 package dp; import java.io.BufferedReader; import java.io.IO..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net -문제해설 처음 문제를 읽었을 때 강수량이 안나와있어서 당황했는데 걍 0부터 입력값 max까지 반복하면 되는 거였다 첫 번째는 bfs로 문제를 풀었다. 반복문이 많아서 시간초과 나오지 않을까 걱정했는데 빨리 채점됐다.ㅎ 대략적인 로직은 다음과 같다. 1. 배열 입력을 받을 때 미리 가장 큰 값을 max에 저장시킨다. (강수량을 0부터 max까지 반복하기 위해서) 배열 입력값은 arr에 저장된다. 2. 강..

https://www.acmicpc.net/problem/1874 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까지 오름차순으로 숫자를 집어넣으면서 push와 pop을 반복하여 입력받은 값들과 똑같이 만들면 되는 문제이다. 자바코드에서 첫 번째 풀이는 먼저 다 입력을 받고 하나하나 비교해나가는 풀이이고 두 번째 풀이는 다른 사람풀이를 참고하여 하나씩 입력받을 때마다 스택을 push, pop하는 코드..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net -문제해설 아직 이분탐색이 익숙하지가 않나보다. 한참 헤매다가 풀었다.. 처음 입력받을 때 가장 큰 값을 찾기위해서 입력값에 대해서 Math.max() 메소드로 최대값을 찾아주고 이분탐색을 위해 start = 0, end = max값으로 설정한다. 그리고 while의 조건으로 start가 end보다 작거나 같으면 반복되도록 한다. while문 안에서는 중간값을 찾기 위..