골란디 / 제한시간: 45분
https://www.acmicpc.net/problem/2086
2086행: 피보나치 수의 합
1항과 2항을 1이라고 하고, 3항에서 앞의 2항의 합을 취하는 수열을 피보나치 수열이라고 합니다.
예를 들어 세 번째 항은 2이고 네 번째 항은 3입니다.
피보나치 수열의 a 번째 항에서 b 번째 항까지
www.acmicpc.net
(AC)
솔루션 프로세스:
– 피보나치의 합에 대한 재귀 방정식의 유도는 S(n)=f(n+2)-1입니다.
– 피보나치 수는 Matrix Divide and Conquer로 빠르게 얻을 수 있습니다.
https://www.acmicpc.net/problem/1525
1525호: 직소 퍼즐
3줄 표에 입력된 9개의 숫자를 얻습니다.
한 줄에 세 개의 숫자가 주어지고 빈 셀은 0으로 표시됩니다.
www.acmicpc.net
(AC)
솔루션 프로세스:
– 그리드의 경우의 수가 9이기 때문에 BFS!
– 그리드 자체를 맵의 키로 받아서 코드를 작성했는데, 메모리 제한으로 인해 그리드를 정수로 대체했습니다.
https://www.acmicpc.net/problem/17436
#17436: 소수의 배수
N(1 ≤ N ≤ 10) 및 M(1 ≤ M ≤ 1012)은 첫 번째 줄에 지정됩니다.
두 번째 행에는 N개의 소수가 포함됩니다.
입력으로 지정된 소수는 100 이하이며 동일한 소수는 두 번 이상 지정할 수 없습니다.
www.acmicpc.net
(AC)
솔루션 프로세스:
– 포함/배제 원칙
https://www.acmicpc.net/problem/23326
23326: 홍익관광객
도현은 홍익관광객이 되어 홍익대학교에 진학하고 싶어한다.
홍익대학교에는 $N$의 학군이 원형으로 배열되어 있습니다.
$1$ 영역에서 시계 방향으로 $2$, …, $N$ 영역이 있고,
www.acmicpc.net
(AC)
솔루션 프로세스:
– 랜드마크가 되는 포인트를 문장으로 관리하면서 2부 검색으로 얻었습니다.
https://www.acmicpc.net/problem/1516
1516호: 게임 개발
건물 유형의 수 N(1 ≤ N ≤ 500)은 첫 번째 줄에 제공됩니다.
다음 N 라인은 각 건물을 짓는 데 걸리는 시간과 지을 수 있기 전에 지어야 하는 건물의 수를 나타냅니다.
건물 번호 1
www.acmicpc.net
(AC)
솔루션 프로세스:
– 토폴로지 정렬
https://www.acmicpc.net/problem/14941
#14941: 호기심
질문 수 n은 첫 번째 줄에 지정됩니다.
다음 줄부터 함수의 입력 a와 b가 차례로 지정됩니다.
(1 ≤ a ≤ b ≤ 105) 남규는 호기심이 많아서 질문을 많이 한다.
따라서 질문의 수는 n
www.acmicpc.net
(AC)
솔루션 프로세스:
– 소수 전처리 후 간단하게 계산하세요.
https://www.acmicpc.net/problem/18869
#18869: 멀티버스 Ⅱ
M개의 우주가 있고 각 우주에는 1부터 N까지 번호가 매겨진 N개의 행성이 있습니다.
행성의 크기를 알면 비슷한 우주가 몇 쌍이나 있는지 알아내려고 합니다.
구성은 같지만 순서가 다른 한 쌍의 우주
www.acmicpc.net
(AC)
솔루션 프로세스:
– {행성 크기, 행성 번호}로 정렬 시 모든 행성 번호가 일치해야 하며, 행성 크기 좌표 압축 값이 동일해야 합니다.