문제 링크 https://www.acmicpc.net/problem/15924 구사과씨가 어디서 출발할지 모른다. 따라서 각각의 모든 점에서 X까지 갈 수 있는 경우의 수를 모두 구해서 더해야 한다. 역으로 X에서부터 시작해 뒤쪽에서 앞쪽으로 올 수 있는 경우의 수를 저장하자. $d[i][j] = (i, j)$에서 X까지 갈 수 있는 경로의 수 $p[i][j] = $ 직사각형 지도에서 $(i, j)$의 정보 $\left\{\begin{array}{c}d[i-1][j] = d[i-1][j] + d[i][j],\text{ if }\ i - 1 \geq 0 \text{ and } p[i-1][j] = \text{'S' or 'B'} \\ d[i][j-1] = d[i][j-1] + d[i][j],\text{ i..
문제 링크 https://www.acmicpc.net/problem/15922 문제를 풀기 위해 수직선들을 좌표가 낮은 순으로 정렬하자. 그리고 앞의 수직선부터 탐색한다. 인접한 두 수직선의 관계는 다음과 같다. 빨간 선의 양 끝점을 $s$, $e$라 하고 파란 선의 양 끝점을 $ns$, $ne$라 하자. ①은 $s \leq ns\ \& \ ne \leq e$인 경우이고, 더 작은 선분을 무시하는걸로 해결할 수 있다. ②는 $ns < e$인 경우이고, 두 선분의 길이의 합에 중복된 $e - ns$의 값을 빼줌으로써 해결할 수 있다. ③의 경우엔 그냥 둘 다 더하면 된다. 파란 선은 현재 내가 보고있는 선분, 빨간 선이 파란 선분의 바로 직전 선분이다. 정답 코드 질문, 피드백 환영합니다.
문제 링크 https://www.acmicpc.net/problem/15921 힌트에 괜히 쓸데없는 말을 집어넣어서 평균과 기댓값을 구하도록 유도하는데 굳이 그럴 필요 없다. 기댓값 $E(X) = \sum\nolimits_{i}p_ix_i$이고 어떤 수 x가 수열에 등장할 확률 $P(x) = \dfrac{\text{x의 등장 횟수}}{\text{전체 수열의 길이}}$ 이다. x의 등장 횟수를 $c$라 하고 전체 수열의 길이를 $n$이라 하면 $P(x) = \dfrac{c}{n}$ 이고 이때 $px = \dfrac{cx}{n}$인데, 이는 $\dfrac{x}{n}$ 을 $c$번 더한 것과 같다. 결국 기댓값 $E(X) = \sum\nolimits_{i}\frac{x_i}{n}$이므로 평균과 다를 바 없기 ..
문제 링크 https://www.acmicpc.net/problem/15920 단순 구현? 시뮬레이션? 문제다. state를 정의하자 state == 0 일때 마네킹 5개가 날아가고 state == 1 일때 마네킹 1개가 날아가고 state == 2 일때 마네킹 6개가 모두 날아가는 걸로 하자. P가 나올때마다 state의 상태를 0 ~ 1 사이에서 반전시키는데, W가 한 번 나온 상황에서 P가 나온다면 state를 2로 고정시키자. W가 2번 나왔을 때 답을 출력하고 종료하자. 정답 코드 질문, 피드백 환영합니다.
문제 링크https://www.acmicpc.net/problem/15917 어떤 수 a가 2의 거듭제곱꼴인지 판별하면 된다.쿼리의 수 Q가 $1 \leq Q \leq 1,000,000$이므로 단순히 a의 비트를 순회하며 1이 하나인지 확인해도 $O(32Q)$이므로 충분하다.좀 더 효율적으로 하고싶다면 $a\ \&\ (a - 1)$이 0인지 확인하자.모든 양수 a에 대해 a가 2의 거듭제곱꼴이라면 위의 값이 0이 나온다. 글을 쓰면서 문제를 다시 확인했는데 힌트 부분에 이미 답이 나와있었다... 닉값하는 문제;; 정답 코드 질문, 피드백 환영합니다.
문제 링크https://www.acmicpc.net/problem/15916 평면 위의 점들을 이은 그래프와 한 직선 $y = kx$가 주어졌을 때 $(0, 0)$이외의 점에서 한 번이라도 직선과 그래프가 만나는지를 확인하면 된다. CCW를 이용해 선분의 교차를 확인하자. 우선 직선과 선분의 교차 여부를 판단하기는 어려우니, 선분과 선분의 교차 여부를 확인하기 위해 $y = kx$를 선분으로 만든다. 평면 위 점들의 y좌표가 $0 \leq y \leq 2^{30}$ 이므로 직선 위의 점 중 $y' > 2^{30}$ 를 만족하는 적당한 점$(x',\ y')$와 $(0, 0)$을 이어 선분으로 만들면 된다. $x' = \dfrac{2^{31}}{k}$ $y' = kx'$ 정도가 좋겠다.수학적 나눗셈이 아닌 ..
문제 링크https://www.acmicpc.net/problem/1010 다음과 같은 그림에서 서쪽 사이트의 개수만큼 다리를 지으려 할 때 겹치지 않게 다리를 모두 지을 수 있는 경우의 수를 구해야 한다. 다리끼리는 서로 겹쳐질 수 없다라는 조건이 있다. 이런 경우는 가능하지만 이런 경우는 불가능하다는 것이다. 서쪽 사이트의 집합을 $A$, 동쪽 사이트의 집합을 $B$라 하면 $1 \leq i, j \leq N$ 인 $i,\,j$와$1 \leq x, y \leq M$ 인 $x,\,y$에 대해 $A[i]$와 $B[x],\,A[j]$와 $B[y]$가 연결된다면 항상 $i
문제 링크 https://www.acmicpc.net/problem/12888 간단해 보이니까 머리를 싸매고 잘 생각해보자.. 어... 음... 헷갈린다. 이럴땐 그림판으로 그림을 그려보면 된다. 와! 규칙을 찾았다! $i$가 홀수일 때 $d[i] = (d[i-1] - 1)*2 + 1 = d[i-1]*2 - 1$ $i$가 짝수일 때 $d[i] = d[i-1]*2 + 1$ 그대로 코드로 옮기면 된다. 단, $0 \leq n$이므로 $n = 0$인 경우도 구해줘야 한다. 답이 나올 수 있는 범위는 long long 범위인 것도 확인하자. 정답 코드