목록알고리즘/문제 풀이 (64)
Joonas' Note
링크: https://www.acmicpc.net/problem/2887 모든 행성을 터널로 연결할건데, 그 비용의 합이 최소가 되게 만드는 최소 스패닝 트리 문제이다. 문제는 \(N\)이 너무 커서, 행성 사이의 간선을 전부 살피는 건 힘들다는 것이다. 두 행성 A와 B의 거리를 \(min(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)\) 로 정의했기 때문에 어떤 행성에서 가장 가까울 행성의 후보가 확 줄어든다. 행성 A에서 가장 가까운 행성 B는 \(|x_A - x_B|\)가 최소이거나 \(|y_A - y_B|\)가 최소이거나, \(|z_A - z_B|\)가 최소인 것 3개 중 하나이다. \(x, y, z\)마다 정렬하면 된다.
링크: https://www.acmicpc.net/problem/2718[이전 게시글로부터 글 옮김]2x1 크기의 타일로 4xN 크기의 타일을 채우는 경우의 수를 구하는 문제이다.문제를 작은 문제로 쪼개야하는 데 발상보다는 과정이 쉽게 떠오르지 않아서 해결하는 데 오랜 시간이 걸렸다.2xN 타일 크기의 문제와 똑같이 왼쪽부터 1줄씩 채워나가면서 완성해나간다. 하지만 이 문제는 높이가 4N이기 때문에 1줄을 채울 때 여러 개의 경우가 나온다. [그림 1] 한 줄의 상태를 비트로 표현할 때의 정수 외의 경우(1010 이나 0001 등의 형태)는 나올 수 없다. 왜냐하면 "이전의 줄의 모든 칸은 채워져있다."라는 가정에서 나타나는 상태이기 때문이다. 이 가정이 성립하지 않으면 타일은 채워질 수 없다. [그림 ..
문제링크: https://www.acmicpc.net/problem/9373복도에 센서들이 있고 센서들을 피해 복도를 통과할 수 있는 가장 큰 원의 반지름을 구하는 문제이다. 복도의 너비가 주어지고, 각 센서들의 좌표 x, y와 반지름 r이 주어진다.처음에는 센서와 센서 사이에 존재할 수 있는 원들로 어떻게 MST를 잘 만들면 되지 않을까했는데, 가장 큰 원의 반지름을 구하기가 힘들었다. 하루 정도 계속 틀리고 고민하고를 반복하다 솔루션을 찾아봤다. 솔루션을 보자마자 와 이게 뭐지 싶었다. 이렇게 풀 수도 있구나 신기했다.풀이최소 신장 트리 문제는 맞았고 원과 원 사이의 끼인 원으로 어떻게 하는 것도 맞았다. 근데 최종형태가 이런 식이었다.양쪽 벽을 큰 집합이라고 생각하고 두 집합이 연결될 때까지 MST..
문제 링크 : http://119.201.123.184/30stair/sumofinte/sumofinte.php 정답 코드 중에서 실행 시간이 644ms로 1위다. 이럴 날이 별로 없어서 캡쳐 주륵..문제수열의 길이 N과 질문의 수 Q가 주어지는 데, 둘 다 N, Q sum = L.sum + R.sum
[이전 블로그로부터 글 옮김] GCJ 링크 : https://code.google.com/codejam/contest/6254486/dashboardProblem A - Counting SheepN이 주어지면 N, 2N, ..., kN까지 진행했을 때, 0~9을 모두 사용하게 되는 시점 k에서의 kN을 구하는 문제이다. 문제 그대로 시뮬레이션하면 된다. large set에서 범위가 \(0 \le N \le 10^6\) 이지만 0~9가 모두 나오게 되는건 최대 100배이므로 int 범위로 충분히 표현할 수 있다. Problem B - Revenge of the Pancakes앞에서부터 k번째까지를 뒤집을 수 있다. (0~k 를 k~0으로 뒤집고 모든 -를 +로 뒤집는다. +-- 를 전부 뒤집는다면 ++- ..
[이전 블로그로부터 글 옮김] Online Judge: https://www.acmicpc.net/contest/view/152 크롬에서 한국어 번역 기능을 써서 문제를 읽었다. 문장이 이상하면 영어로 번역했다. 문제 #1. 科目選択(물리, 화학, 생물, 지구과학) 중 상위 점수 3개 + (역사, 지리) 중 상위 점수 1개 두 묶음을 나눈 뒤 정렬하고 더함. 문제 #2. ゼッケンの交換문제에서 설명한대로 구현하면 정답. a[j] mod k > a[j+1] mod k 이면 자리를 바꾼다. k를 2부터 m까지 진행한 후 배열 a의 상태를 출력한다. 문제 #3. ロシアの旗주어진 국기를 러시아 국기의 형태로 바꿔야하는 데, 최소 몇 개의 칸의 색깔을 바꿔야 하는 지 출력하는 문제이다. 위에서부터 (흰색, 파란색,..
[이전 블로그로부터 글 옮김] 문제적남자 73화 - 수학 풀이 수능 D-100 특집으로 이런 문제가 나왔다. 첫 번째 숫자까지는 1로 나누어지고,두 번째 숫자까지는 2로, .... 열 번째 숫자까지는 10으로 나누어진다.0부터 9까지 10개의 숫자를 모두 사용해 규칙에 맞는 수를 만들어라. 다음과 같은 몇 가지 규칙을 발견하고 브루트 포스로 풀어보기로 했다. 1. 열 번째 숫자는 0 이다. (10의 배수는 0으로 끝나기 때문)2. 다섯 번째 숫자는 5 이다. (5의 배수는 0, 5로 끝난다. 0은 열 번째 숫자이므로 5)3. 짝수 번째 숫자는 2, 4, 6, 8 중 하나이다.4. 홀수 번째 숫자는 1, 2, 3, 4, 6, 7, 8, 9 중 하나이다. 소스: https://jsfiddle.net/J00n..
[이전 블로그로부터 글 옮김] 이 내용은 Beakjoon Online Judge, Algospot 등의 온라인 저지를 사용하시는 분들에게 도움이 될 내용입니다. 최근들어 컴파일에러로 오답을 받고 질문을 올리시는 분이 자주 보이는 것 같습니다.주로 그 내용은 "비주얼 스튜디오에서는 되는 데 백준에서는 오류가 나네요" 등이더군요.컴파일 에러를 해결하시는 데에 도움이 될 만한 글을 남기고자 합니다.비쥬얼 스튜디오에서는 되는 데..비쥬얼 스튜디오는 생각 이상으로 강력한 통합 개발 환경(IDE)을 제공합니다. 아래 코드는 컴파일 에러일까요?#include int main() { printf("%d", strlen("123")); return 0; }위 코드는 컴파일 에러가 맞습니다. strlen 함수는 cstri..