개발하는 고라니

1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net [비트마스킹] 정수형 배열을 하나 준비한다. 사이즈는 대충 16이상이면 된다. 배열의 0 번째 원소에 1 x라면 idx를 감소시킨다. 이제 비트 연산자를 이용해 arr[idx] = (arr[idx-1] >> 1); arr[idx-1] = (arr[idx-1] >> 1); idx번 째와 idx-1번째 원소를 idx-1번째에 있는 원소를 반으로 나눈 값으로 설정한다. sum == x일 때 까지 반복 # Code import java.io.BufferedReade..

16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net [BFS] 문제의 난이도는 그렇게 높진 않으나 접근하기가 까다로웠다. 각 층은 4방향을 가질 수 있고, 1~5층에 어떤 것을 넣든지 사용자의 결정이다. 사실상 브루트포스로 풀었다. 먼저 입력을 받을 때 원 방향, 90도, 180도, -90도 회전시킨 판의 모양을 저장한다. for(int i=1; i

16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net [BFS] 사람이 먼저 BFS 탐색을 하고, 그 다음 벽이 움직이는 벽 BFS가 실행된다.이 문제에서, 벽은 8턴 이후에는 맵에 없으므로(8줄이기 때문에 8턴 후 모든 벽은 사라진다) 9턴 째 까지 왔다면 탐색할 필요 없이 탈출에 성공한 것이다. 그래서 visit배열을 3차원 배열로 선언해 몇 번째 턴일 때 방문한 것인지 체크하였다. 플레이어는 상하좌우, 대각선, 제자리 이렇게 9곳을 탐색할 수 있다. 그리고 가장중요한 것은 다음과 같은 상황일 때의 처..

13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net [Collection 사용] 사실 이 문제의 알고리즘 카테고리는 '비트마스킹'이지만,,, 비트마스킹으로 어떻게 풀어야할지 몰라 3가지 방법으로 풀었다. 1) Set 2) boolean[] 3) Map 방법은 간단하다. 각 자료구조에 특정 값이 없다면 추가하고, 특정 값이 있다면 스킵한다. # Code 1) Set public static void main(String[] args) thr..

1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [소수 판정] 1부터 n까지 반복문을 돌며 소수인 것을 prime 배열에 저장했다. 그러면 prime에는 n이하의 소수만 저장되게 된다. 이제 이중 루프를 이용해서 prime을 돌며 연속 합이 n보다 같은 경우를 찾아 count를 증가시킨다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static boolean isPrime(int x){ if(x == 1) return false; for(int i=2; i

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net [소수 판별] 소수를 판별하는 간단한 알고리즘은 특정 숫자 x에 대해 2 ~ x의 제곱근까지 나머지연산을 해보며 결과값이 0이면 소수가 아니라고 판별한다. 자바의 경우 출력이 많을 수 있으므로 System.out.println()을 이용한다면 메모리와 시간을 많이 잡아먹는다. 따라서 StringBuilder를 이용했다. 혹시 메모제이션으로 할 수도 있지 않을까 했지만 굳이 필요는 없었다. import java.io.BufferedReader; import java.io.IOException; ..

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net [소수 판별] 정수 x를 입력받아 소수인지 확인하는 방법은 2부터 x의 제곱근까지의 수를 x와 나머지 연산했을 때 결과가 0이면 소수가 아니라고 판별한다. # Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int cnt = 0; static boolean isPrime(int x){ if(x ==..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net [BFS] 정답률 25%를 과시라도 하듯 결코 쉽지않은 문제이다. 문제에 주어진 조건 중 몇 가지가 특히 어떻게 접근해야할지 난해했다. 그 중에 '빨간 구슬(R)과 파란 구슬(B)은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다.' 가 특히나 골치아팠다. static class Point{ int y, x; public Point(int yy, int xx){ y=y..