[백준 / BOJ] 1030 프렉탈 평면 (Java)
문제 출처 : https://www.acmicpc.net/problem/1030 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 7개의 정수 s, N, K, R1, R2, C1, C2 가 주어진다. 1*1그리드는 매 초마다 N*N그리드로 나뉘어지며 이때, 나뉜 정사각형이 흰색이라면, 가운데 K*K칸이 검은색으로 변한다. s초가 지났을때, R1,C1에서 R2,C2그리드를 출력하는 문제다. 풀이 수학?과 분할정복으로 푸는 문제였다. 문제를 풀기위해 우선, N*N 그리드가 매초마다 K*K조각으로 나누어질때, s초가 지난후 위치하는 좌표를 구해야한다. 예를들어, 1*1그리드가 매 초마다 3*3의 조각으로 나뉠때, 2초가 지난후 ..
[백준 / BOJ] 15732 도토리 숨기기
문제 출처 : https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 수형이는 N개의 상자에 도토리를 숨기려한다. 이때, 도토리를 숨긴위치를 기억하기 쉽게하기위해 규칙있게 숨긴다. 예를들어, A상자부터 B상자까지 C간격으로 도토리를 숨긴다면, A 상자에 하나를 숨기고, A+C상자에 하나를 숨기고, A+2C상자에 하나를 숨기고..B상자에 마지막하나를 숨긴다. 상자의 수..
[백준 / BOJ] 1253 좋다
문제 출처 : www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net N개의 수열이 주어진다. 이때, N개의 수 중에서, 어떤 수가 다른 수 두개의 합으로 나타내진다면, 그 수를 좋다 라고한다. 좋은수가 몇개인지 구하는 문제다. (위치가 다르면 값이 같아도 다른 수 이다.) 풀이 완전탐색으로 풀경우 O(N^3)이 되어서 시간초과가 난다. 시간초과를 피하기 위해, 이분탐색으로 풀은 문제다. 로직은 간단한데, 수열 N에서 i번째수를 Ni라 할때, 1. 좋은 수 인지 판단할 수 Ni를 하나 지정한다..