백준 (227) 썸네일형 리스트형 백준 9825 - MODSUM https://www.acmicpc.net/problem/9825 문제를 보면 다음과 같이 언급하고 있다. Important note: You can assume that the result will always be less than 1,000,000. 이 말을 통해 문제에서는 연산의 제한이 $10^{6}$임을 암시하고 있다. 문제에서 제시한 계산식 \[\sum_{x_1 = v_1}^{w_1}\sum_{x_2 = v_2}^{w_2} \cdots \sum_{x_n = v_n}^{w_1} f(x_1, \dots, x_n)\] 으로만 보면 많은 연산이 필요할 것으로 보이나, 제한을 걸고 있기 때문에 안심하고 브루트포스를 해도 되는 것으로 이해할 수 있다. 문제의 제한을 이해했으므로 나머지는 신경 쓸 필요.. 백준 1069 - 집으로 https://www.acmicpc.net/problem/1069힌트더보기제목 그대로 집으로 가는 방법은 몇 개가 있을까? 넓은 관점으로 생각해본다.풀이더보기다음 그림을 보면 이 문제에 대한 핵심을 쉽게 이해할 수 있다. 위 그림을 보면 알 수 있듯이, 목표를 향해 일직선으로 가는 것보다 점프를 2번 해서 가는 방법이 더 빠른 경우가 존재할 수 있다. 우리는 이 사실을 반영하여 목표로 향하는 최소 시간을 구하기 위해 다음 두 방법을 섞었을 경우를 계산할 것이다. 1. 목적지까지 일직선으로 걷기 또는 점프하는 시간2. 목적지에 도착하기 위해 두 번 점프하는 시간 일단 초기해를 피타고라스의 정리로 계산한 두 지점 간의 일직선 거리 $(dx^{2} + dy^{2})^{\frac{1}{2}}$로 설정한다. 그.. 백준 27437 - 분수찾기 2 https://www.acmicpc.net/problem/27437힌트더보기문제에 그려진 테이블을 유심히 보자. 위와 같이 구분한다고 했을 때 패턴을 찾아낼 수 있는가?풀이더보기위 힌트에서 주어진 테이블을 대각선으로 나눴다. 그러면 우리는 각 대각선에서 발견할 수 있는 중요한 성질을 다음과 같이 정리할 수 있다. 각 대각선에 속한 수들의 집합을 $D_{1}, D_{2}, D_{3}, ...$으로 부르며 원소의 갯수는 $1, 2, 3, ...$이다. 이때 $D_{i}$의 원소인 $\frac{y}{x}$에서 $MAX(x, y) = i$이다. 우리는 $\sum_{i = 1}^{n}\nolimits i \leq X$를 만족하는 $i$의 최댓값을 파라메트릭 서치로 찾아낼 수 있다. 그리고 대각선을 문제의 규칙에.. 백준 32250 - Super Shy (Easy) https://www.acmicpc.net/problem/32250힌트 1더보기만약 먼저 앉은 사람이 아무도 없을 경우 아무 자리에나 앉을 수 있다. 이 조건이 대단히 중요하다.힌트 2더보기최초로 사람을 배치한 이후, 규칙에 따라 사람을 배치하는데 나타나는 성질을 찾을 수 있는가?풀이더보기먼저 사람을 아무 곳에 배치한다고 해보자. 그러면 그 사람을 기준으로 나눈 왼쪽 구간과 오른쪽 구간 $L$과 $R$을 얻을 수 있다. $L$과 $R$에서 사람을 배치할 때는 문제의 규칙에 의해 다음과 같은 성질을 발견할 수 있다. 구간 $L, R$에서 첫 번째 사람이 놓인 기준점을 포함하여 각 사람과의 거리는 2 또는 3이다. 이는 거리를 가능한한 멀리 떨어트려야 한다는 조건을 만족시키기 위해 중앙에 배치하면서 다시 두.. 백준 22221 - Table 1 https://www.acmicpc.net/problem/22221 이런 형태의 문제를 처음 보면 이해하기 어려울 수 있지만 다음과 같이 정리할 수 있다. 1. 숫자를 붙여 N자리 숫자를 만들어야 한다. 2. 각 행(좌에서 우로), 열(위에서 아래로), 그리고 주 대각선을 대상으로 숫자를 이어붙인다. 3. 이렇게 이어붙인 수들은 서로 중복되지 않으며 M의 배수를 만족해야 한다. 4. 0으로 시작하는 수가 있으면 안 된다. 추가로 Table 1에는 점수가 2점 이하라는 조건이 붙는다. 이는 제한에서 다음과 같은 구문을 확인할 수 있다. Otherwise your score for the test case is calculated from the formula: N. N으로 점수를 매긴다는 뜻이다. 따라.. 이전 1 2 3 4 5 6 7 ··· 46 다음
