본문 바로가기

전체 글

 (116)
백준 9556번: 수학 숙제 https://www.acmicpc.net/problem/9556 9556번: 수학 숙제 각 테스트 케이스마다 조건을 만족하는 N자리 정수의 개수를 1,000,000,007로 나눈 값을 출력한다. www.acmicpc.net 처음엔 포함 배제로 풀려고 했다가, 제가 포함 배제에 익숙하지 못해서 구현을 포기하고 다른 방법으로 풀게 됐습니다. 이 문제의 첫 번째 포인트는 $N$자리 수는 한 개 이상의 0으로 시작할 수 있다는 것입니다. 즉 우리가 체크해야 할 수의 범위는 0부터 $10^{N}-1$까지입니다. 두 번째 포인트는 이 문제의 나눠 떨어진다는 표현은 나머지가 0이라는 것입니다. 그래서 0은 모든 양의 정수로 나누어 떨어지는 수라고 합니다. 이 문제는 물론 포함 배제로도 풀 수 있겠지만, 더 쉬운 관..
백준 16201번: 발코니 공사 https://www.acmicpc.net/problem/16201 16201번: 발코니 공사 첫째 줄에 별장 발코니의 크기 R, C와 부서지지 않은 칸의 개수 K가 주어진다. (1 ≤ R ≤ 1,000,000,000, 2 ≤ C ≤ 1,000,000,000, 0 ≤ K ≤ 1,000) 둘째 줄부터 K개의 줄에는 부서지지 않은 칸의 위치가 공백 www.acmicpc.net 도미노의 모양새에 대한 조건이 너무 강력해서 티어가 낮아진 문제입니다. 이 문제는 colorless한 $1 \times 2$ 도미노의 타일링을 다루고 있고 특별한 조건으로 "가로로만 놓을 수 있음"이 있습니다. 또 하나의 조건은 도미노를 최대한 많이 써야만 한다는 것입니다. 그래서 각 row에 대해 총 몇 개의 도미노를 놓을 수 있는지..
백준 26132번: Fair Division https://www.acmicpc.net/problem/26132 26132번: Fair Division After sailing the Seven Seas and raiding many ships, Cap’n Red and his crew of fellow pirates are finally ready to divide their loot. According to ancient traditions, the crew stands in a circle ordered by a strict pirate hierarchy. Cap’n Red starts by www.acmicpc.net 비록 해당 대회에서 제일 약한 급의 문제이긴 하지만 ICPC World Finals 2021 문제입니다! 풀이는 약간의 수학..
백준 16214: N과 M https://www.acmicpc.net/problem/16214 16214번: N과 M 임의의 자연수 N과 M이 주어져 있다. A^B를 A의 B승이라고 할 때, 수열 N, N^N, N^(N^N), N^(N^(N^N)), ... 의 수들을 M으로 나눈 나머지는 수열의 어느 지점부터 항상 일정한 값을 가진다. N과 M이 주어져 있 www.acmicpc.net 일반적인 power tower 유형에서 모든 지수에 $N$을 넣어준 것이므로 난이도가 어떤 면에선 더 쉬워졌다고 볼 수 있습니다. 본문은 매우 훌륭한 자료인 https://rkm0959.tistory.com/181 을 인용했습니다. 위 글에 따르면 다음이 성립합니다. (Notation은 위 링크를 참조해주시기 바랍니다.) $$ [N,N,N, \cdo..
백준 17315번: Matrix Game (integer interpretation) https://www.acmicpc.net/problem/17315 17315번: Matrix Game The input will contain the six integers n, m, a, b, c, and d. www.acmicpc.net National Olympiad in Informatics, China, 2013, Day2에 Problem1로 출제된 문제라고 합니다. 행렬 거듭제곱 풀이에 대해 궁금하신 분은 이쪽 링크를 이용하시면 됩니다:Matrix Game (matrix interpretation) 정수 거듭제곱 풀이는 주어진 규칙대로 끝까지 전개하여 다음 식에서 $f$와 $g$를 구하는 것이 목표입니다. $$ F[n][m] = f(a,b,c,d) \times F[1][1] + g(a,b,c..
백준 14553번: The Way https://www.acmicpc.net/problem/14553 14553번: The Way 여우와 토끼는 사이가 좋았다. 하지만 어느 날 토끼가 여우에게 갓겜 "히어로즈 오브 더 스톰"을 추천했고, 여우는 게임을 해보고 너무 화가나서 토끼를 쫓으러 갔다. 히어로즈 오브 더 스톰의 www.acmicpc.net 처음에 dp 식을 이상한 방향으로 접근해서 오랫동안 힘들었던 문제입니다. 우선 제가 AC 받은 접근은, $3 \times N$ 격자를 가장 왼쪽의 1열에서 2열로 넘어가는 모양새를 기준으로 subproblem을 나눕니다. 이게 무슨 뜻인지 경우의 수를 나누어 설명하겠습니다. 시작하는 칸에서 바로 오른쪽으로 이동 : 2열의 윗 칸에서 N열의 아랫 칸으로 가는 경우의 수 시작하는 칸에서 2열의 가운..
백준 13380번: Found https://www.acmicpc.net/problem/13380 13380번: Found Alice and Bob live in a city with N intersections (numbered as intersection 1, intersection 2,..., intersection N). There are M roads. Each road is bidirectional and directly joins two intersections. Each pair of intersections is joined by at most one road www.acmicpc.net 문제 지문을 읽어보면, $N$개의 intersection이 있고 $M$개의 road가 있고 $T$ 만큼 지난 후에 둘이 만납니다. ..
백준 26035번: $0101$ https://www.acmicpc.net/problem/26035 26035번: $0101$ $N\times M$ 크기의 배열의 각 칸에 $0$과 $1$중 하나를 적는다. 이때, 모든 $2\times 2$ 크기의 부분 배열 안에 적힌 수의 합이 $2$로 같아지도록 배열을 채우는 방법의 수를 구하여라. www.acmicpc.net $N$을 편하게 2로 고정해놓고 $M$을 늘리면서 관찰하면 쉬운 문제입니다. 또한, 관찰할 때 저의 경우 위에서부터 1행을 채우고 그 아래 행을 채운다는 느낌으로 접근했습니다. 예제에 나온 $M=4$, $N=2$의 경우를 한 번 보게 되면 1행이 $0101$, $1010$일 경우를 제외하고 모두 1행이 정해지면 2행도 단 하나로 결정됐습니다. $M=3$인 경우 $101$, $0..

티스토리툴바