3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net IDEA 성냥개비는 2개부터 주어진다. 1개의 성냥개비로는 만들 수 있는 숫자가 없다. 각 숫자를 만드는데 필요한 성냥개비의 수는 다음과 같다. 1 2 3 4 5 6 7 8 9 0 2개 5개 5개 4개 5개 6개 3개 7개 6개 6개 큰수를 만들기 위해서는 가능한 자릿수를 많게, 앞자리를 크게 해주면 된다. 단 2개의 성냥개비만 있으면 자릿수를 하나씩 늘려버릴 수 있다. 한개만 더 있으면 맨 앞자리를 1에서 7로 바꿀 수 있다. 가장 큰 숫자를 만들기는 이렇게 간단히 ..

1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net IDEA 자료를 입력 받음과 동시에 정렬을 해내야하는 문제다. 중앙값을 입력과 동시에 최신화 해주어야하기 때문에 자료는 항상 중앙값에 한해 정렬된 상태를 유지한다. "어떤 자료 구조를 사용하고 어떻게 입력을 받아 정렬 상태를 유지해낼 것이냐"가 이 문제의 빡센 0.1초의 시간 제한을 뚫을 수 있냐 없냐를 결정하는 문제다. 먼저 일반적인 배열을 떠올렸다. 가장 작은 값이 맨 앞으로 오는 오름차순 정렬을 유지한다. 매 N번째 입력마다 Binary S..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 1번부터 시작해야겠다. 모든 정점 V가 범위 내의 정점 V + 1, V - 1, V * 2 와 연결되어있고 가중치는 1이다. BFS로 탐색을 시작해서 찾는대로 시간을 출력하게 하면 될 것 같다. using System; using System.Collections.Generic; class Program { static int n, k; static int[] time = new int[100001]; static bool[]..

1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net IDEA 9376번 탈옥 문제를 보다가 난 아직 준비가 덜 된 것 같아서 분류되어있는 더 쉬운 문제를 찾다 풀게 되었다. 다익스트라 알고리즘의 한 종류인데 특이하게 가중치가 0, 1 밖에 없다. '0-1 너비우선 탐색' 문제다. 이건 BFS로 해결할 수 있다. 정석적인 풀이를 찾아보려고 고수님들의 설명을 찾아보다 justicehui님의 깃허브 페이지에 있는 글을 발견했다. 요약하면 그래프 G에 V개의 정점, E개의 간선이 있고 가중치는 0,..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net IDEA 두 알고리즘은 이름에서 나타내는 것처럼 탐색의 우선순위가 다르다. 최초 탐색 지점에서 연결된 곳들을 순차적으로 확인하는 너비우선탐색(BFS)은 한 계층의 정점을 모두 확인하고 다음 계층으로 내려가기 때문에 최단거리를 찾는 탐색에서 유리하다. 깊이우선탐색(DFS)은 탐색 경로를 기억해둬야할 때 유리하다. 모든 정점을 탐색해야하는 문제에서는 어떤 알고리즘을 선택해도 시간복잡도 상의 차이는 없다. 이 문제는 모든 정점을 탐색해야하는 문제이기 때문에 너비우선탐색, 깊이우선..

11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net IDEA 이항 계수를 구하는 문제다. 간단한 다음 공식을 사용하면 바로 해결 가능하다. 그런데 여기서 간단하지 않은 것은 주어진 N의 최댓값이 1,000이다. 20!만 계산해도 long의 표현 범위를 넘어가버린다. 그래서 이 문제에도 분할 정복을 사용해야한다. 그리고 값을 10,007로 나눈 나머지를 출력해야한다. 연산을 모두 끝내고 한꺼번에 나머지를 출력하기엔 너무 큰 숫자를 처리하기 어려울 것 같다. 모듈러 연산을 이용하면 좋겠지만 나눗셈에 대한 모듈러 연산은 없다. 페르마의 소정리에 따르면 어떤 수 a가 정수이고 p가 소수일 때..

18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net IDEA 현재 위치에서 1~N까지의 범위 안에 자유롭게 이동이 가능하다. 브루트포스로 작성하는 것도 가능하겠지만 기상청 컴퓨터를 빌려써야 할 것 같다. N개의 징검다리가 있을 때, N이 1이라면 출발점과 도착점이 같은 것이기 때문에 경우의 수는 1이고 2 이상일 때부터 출발점과 도착점 사이의 징검다리들을 각각 밟을 것인지 건너 뛸 것인지 선택하는 것과 같다. N - 2 개의 징검다리 중 1개만 밟는 경우, 2개만 밟는 경우, 3개만 밟는 경우, ..., N - 3 개를 밟는 경우, N - 2개를 모두 밟는 경우를..

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net IDEA 만약 문제가 "얼음이 전부 녹는 데 걸리는 시간은?" 이었다면 정말 간단히 풀 수 있는 문제다. 이 문제의 함정은 얼음이 녹을 때마다 백조가 만날 수 있는지 없는지 여부를 확인한다는 것에 있다. 여기서 '매일 녹여보고 확인해보면 되지 않을까?' 생각했지만 호수의 범위가 가로 1~1500칸, 세로 1~1500칸이다. 만약 이 방법을 사용한다면 최대 225만칸을 확인해야하는데 무조건 시간초과가 나올 것이다. 다른 분들의 풀이를 ..