2/26

- boj 12905 wa, 골3

$i$번째 사람이 'L'이라고 말한다면 $i$번째 사람과 $i + 1$번째 사람은 서로 다른 상태의 사람이다.

$i$번째 사람이 'H'라고 말한다면 $i$번째 사람과 $i + 1$번째 사람은 같은 상태의 사람이다.

'상태'는 거짓말만 하는 사람이거나 진실만 말하는 사람이다.

이를 이용해 주어진 문자열을 순회하며 배열 $v$에 상태를 채우고, $i$번째 사람이 '?'라고 말한다면 $i + 1$번째 사람은 거짓말 또는 진실을 말하는 상태가 될 수 있기 때문에, 문제에서 요구하는 거짓말쟁이 사람 수의 최솟값을 위해 항상 $i + 1$번째 사람은 진실을 말하는 사람이라고 정한다.

이렇게 다 채우면, v[0]과 v[v.length-1]을 비교해 같다면 그때 거짓말을 하는 상태의 개수를 출력하고 같지 않다면 문자열에 '?'가 1개라도 있었는지 검사한다. '?'를 항상 진실을 말하는 상태로 정했기 때문에 만약 '?'가 1개 이상 있다면, '?' 1개를 거짓말을 하는 상태로 바꿔서 이후 상태들에 대해 홀짝성을 바꿀 수 있다.

그렇지 않다면 -1을 출력한다.

그런데, wa를 받았다! 어째서..?

- boj 23271 ac, 골4

내 기준 골드에서 골때리는 문제 원탑이다. 좌표평면상에서 원 여러 개가 주어졌을 때, 겹치는 걸 고려해서 차지하는 총 면적을 구해야 한다.

골드면서 적분까지 해야 하는 문제인가.. 하면서 얼탱이가 없었는데 알고 보니 $0 \le x, y, r \le 10$이라는 조건이 있었고, 이걸 이용해서 무작위로 범위 내에서 선택된 점이 원 안에 속하는지 확인하는 방식으로 $(\text{범위 면적} \times \text{점이 원 안에 속하는 비율}) = \text{답}$을 만들어 낼 수 있었다.

사실 점을 여러 번 찍어서 그 넓이를 근사하는 방식은 꽤나 널리 알려진 방법이지만, 이걸 여기서 써먹다니..