본문 바로가기

홀짝성3

백준 2873 / C++ https://www.acmicpc.net/problem/2873 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net [ 풀이 ] 홀수인 변이 있다면 전부 방문할 수 있음은 자명하다. 모두 짝수인 경우의 문제를 풀자. 규칙을 찾아보자. 전부 방문하는건 불가능하다. 증명은 다음과 같다. 전부 방문하려면 (r-1)(c-1)개의 화살표가 필요하다. 이 값은 홀수이다. 그런데 시작점에서 끝점으로 가는데엔 짝수번의 화살표가 필요하다. 따라서 홀짝성에 위배된다. 그럼 되도록 1개만 제외하고 방문하고 싶다. 이런 문제의 .. 2022. 8. 12.
백준 16118 / C++ https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net [ 풀이 ] 여우는 v로 가고 늑대는 2v v/2 를 반복한다. 이 때 시간은 여우는 d/v , 늑대는 2d/v 또는 d/2v가 걸린다. 모두 정수로 맞춰주면, 시간은 여우가 2t 2t .... 늑대는 t / 4t / t / 4t .. 이렇게 걸린다. 여우의 경우 그냥 다익을 돌려주면 최단시간이 나온다. 늑대의 경우가 이 문제의 핵심이다. .. 2022. 7. 15.
백준 25339 / C++ https://www.acmicpc.net/problem/25339 25339번: 반전 수와 쿼리 1부터 $N$까지의 수가 한 번씩 등장하는 수열 $P = \lbrace 1, 2, \cdots, N \rbrace$이 주어진다. 수열 $P$에 대해, $i P_j$를 만족하는 순서쌍 $(i, j)$의 개수를 $P$의 반전 수라고 정의하자. 이 www.acmicpc.net 쿼리마다 반전수의 홀짝성을 확인해주는 문제이다. 수학이 전부인 문제. [ 풀이 ] // 1번 쿼리의 경우 Ai와 Aj를 교환한다고 하자. Ai와 Aj 사이의 수열에만 관심이 있다. 나머지 A1~Ai-1, Aj+1~An은 Ai와 Aj가 교환되도 반전수에 영향이 없다. Ai+1~Aj-1중 Ai와 반전쌍을 이루는 것의.. 2022. 7. 12.

티스토리툴바