개발하는 고라니

2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net [이분/이진 탐색, Binary Search] 우선, 이진 탐색을 하기 전 입력받은 각 지방의 예산(arr[])을 모두 더한 값과 국가예산의 총액(limit)을 비교하였다. (총액 >= 예산들의 합) 이라면 예산 중 가장 큰 값을 출력하고 종료한다. 이와 같은 경우가 아니라면 이진 탐색으로 넘어간다. init) left = 1, right = 국가예산의 총액 1) 상한선(mid) 구하기 : mid = (left + right) / n 2) 각 지방의 예산 ..

2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net [DFS] 입력 N은 홀수로만 주어지기 때문에 중간을 (n + 1) / 2로 표현한듯 하다. int[100][2] 배열을 준비하여 int[i][0]에는 i 구슬보다 가벼운 구슬, int[i][1]에는 i 구슬보다 무거운 구슬의 개수를 저장하도록 한다. n회 반복문을 돌며 현재 구슬의 무거운 구슬의 개수 또는 가벼운 구슬의 개수가 (n + 1) / 2개 이상일 때 그 구슬은 가운데의 구슬에 들어갈 수 없다. # Code import java.io..

1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net [플로이드 - 와샬, Floyd - Warshall] A, B, C, D, E가 있다고 하자. A와 B가 친구이고, B와 C가 친구일 때 A와 C는 친구이다. 그럼 C와 D가 친구일 때 A와 D는 친구일까? 아니다. 2-친구이므로 나의 친구의 친구까지만 친구로 인정된다. 따라서 D는 A의 3-친구이다. 이 문제에서는 2-친구만을 답으로 원하므로 플로이드 와샬을 수행하여 각 친구들이 n-친구인지 구하고 2 이하인 친구들의 개수를 구하도록 한다. (0일 때는 친구가 아..

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net [BFS] 4가지의 함수를 구현하기만 하면 간단한 BFS이다. 이 문제의 핵심은 L()과 R()에서 얼마나 시간을 단축하느냐에 달린 것 같다. L, R 함수는 언뜻보면 간단하지만, 항상 4자리임을 가정하고 하는 것이라, 4자리 이하일 때 "0"을 채워 4자리를 만들어줘야한다. 이 과정이 노련한 사람에게는 짧고 간편한 코드로 작성할 수 있겠으나... 나같은 초심자에게는 잡기술을 동원해서 겨우 AC를 받아내었다. static int L(int x){ S..

10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [해싱 + 이진 탐색 (Hashing + Binary Search)] 해싱없이 이진 탐색만으로 값을 검색하면 온전히 모든 값을 다 돌지 못한다. 예를 들어 10이 몇 개 있는지 검색을 할 때 10이 3개 있다고 가정한다면 3개를 모두 돌지 못할 수 있다. 따라서 해싱을 이용해 배열에 해당 값이 몇 개가 있는지 저장해놓으면 편리하다. 나는 다음과 같은 해싱을 사용하였다. 값의 범위는 (-10,000,000 ~ 10,000,000)이..

1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [이분 탐색] 이분 탐색 문제를 풀며 느끼는 거지만, int 보다는 long을 쓰는게 비교적 안전할 것 같다. 세심히 주의를 기울인다면 int를 사용했을 때 overflow가 나오는 것을 캐치할 수 있으나, 작은 수들을 다루다 보면 이를 무심코 지나칠 수 있는 것 같다. 이 문제의 핵심은 (1) left = 1, right = 갖고있는 랜선의 최대 길이 (2) int는 overflow가 발생하므로 long을 사용 (3) N개의 랜선을..

10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [이진 탐색, Binary Search] 그래프 문제를 주로 풀다가 문제의 스펙트럼을 좀 넓혀보고자 이진 탐색 문제를 풀기로 하였다. 이진 탐색의 기본적인 내용을 다루며 응용에 힘쓰도록 한다. 이 문제는 교과서적인 이진 탐색을 물어보는 문제이고, m개의 데이터에 대해 이진 탐색을 수행하면 되므로 딱히 어려울 것은 없어보인다. # Code import java.io.BufferedReader; import java.io.IOExcept..

1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net [BFS] 4자리 이면서 소수인 숫자를 한 자리씩 바꾸는데, 바꿔서 완성된 4자리 수도 소수이어야 한다. 그래서 목표 소수까지 가야하는데, 한 자리씩 어떻게 바꿀 것 인가에 대한 방법은 다양할 것이다. 나는 문자열로 변환하여 풀었다. 예를 들어 1033이라는 수가 있으면, 이를 문자열로 변환하고 1000의 자리, 100의 자리, 10의 자리, 1의 자리에 각각 0~9를 대입하며 (1) 방문했었는지 ? (2) 4자리 숫자인지 ? (3) 소수인지 ? 를 따져서 해당 조건을 ..