이동식 저장소

1개월 반만에 백준 문제를 풀어 보았다. 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 조건을 자세히 읽어 보면, 다음을 관찰할 수 있다. 1. 점프할 때 다른 통나무를 건너뛸 수 없다고 적혀 있지만, 건너뛰는 통나무에 내렸다가 가면 되기 때문에 의미없는 조건이다. 따라서 세로 좌표는 의미가 없고, 가로로만 겹쳐 있으면 이동할 수 있다고 간주해도 좋다. 2. 두 통나무 $A$와 $B$($A.x_1\le B.x_1$)가 있을 때, $A$와 $B$가 가로로 겹칠..

오랜만에 문제를 하나 풀어보자. 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 주어진 규칙으로 채워지는 격자의 일부분을 출력하는 문제이다. 격자의 크기가 $10,000\times 10,000$이므로 격자를 미리 채우는 방법은 시간도 오래 걸리고, 문제의 의도에도 맞지 않다. 이 문제의 의도는 격자에 쓰인 수를 좌표만 가지고 구하는 것이다. 격자를 관찰해 보면, 중심이 같은 정사각형으로 이루어져 있다는 사실을 알 수 있다. 임의의 점 $(r,c)$과 $(0,0)$ 사이의 유클리드 거리는 $max(|r|,|c|)$이다. 이 값을 $d$라고 하고, $(r,c)$가 속한 정사각형의 지름이라고 부르자. 수학적으로는 존재하지 ..

솔루션을 보고 해결한 문제이며, 공부용으로 기록함을 밝힙니다. 12920번: 평범한 배낭 2 (acmicpc.net) 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 12865. 평범한 배낭 문제에서는 모든 물건이 1개였는데, 이 문제에서는 물건이 여러 개일 수 있다. 여러 개의 물건을 처리하는 가장 쉬운 방법은 서로 다른 물건으로 취급하여 푸는 것이다. 그러나 이렇게 풀면 물건이 최대 1만 개이고, 배낭의 무게가 최대 1만이므로 총 1억 번의 계산을 해야 한다. 이러면..

소신발언 시로코라는 캐릭터 처음 봤는데 내 취향 아님 26607번: 시로코와 은행털기 첫 번째 줄에 사람의 수 $n$와 뽑을 인원 $k$, 그리고 힘과 스피드 수치의 합 $x$가 공백으로 구분되어 주어진다. 그 다음줄부터 $n$개의 줄에는 각 사람들이 지닌 힘과 스피드 능력치 $a$ $b$가 주어 www.acmicpc.net 흠흠.. $a+b=x$가 일정한 정수 쌍이 $n$개 주어진다. 그 중 $k$개를 골라서 $\sum _{i=1}^k{a}_i\times \sum _{i=1}^k{b}_i$를 최대화해야 한다. $b=x-a$로 나타낼 수 있으므로 주어진 식을 전개하면 $\sum _{i=1}^k{a}_i\times \sum _{i=1}^k(x-a_i)$이고, $\sum_{i=1..

오랜만에 어려운 거 풀어서 기분이 좋다. 2094번: 강수량 첫째 줄에 정수 n(1 ≤ n ≤ 50,000)이 주어진다. 다음 n개의 줄에는 두 정수 y(0 ≤ |y| ≤ 1,000,000,000), r(1 ≤ r ≤ 1,000,000,000)이 주어지는데, 이는 y년도의 강수량이 r이라는 의미이다. 이러한 정보는 y www.acmicpc.net 문제를 잘 읽고 이 글을 보길 바란다. 정수 $X$와 $Y$가 주어질 때, 다음의 세 가지 조건이 모두 참이어야 주어진 질문에 참이라고 할 수 있다. 구간 $[Y,X]$에 속한 모든 연도의 강수량이 알려져 있어야 한다. $X$년도의 강수량이 $Y$년도의 강수량 이하여야 한다. 구간 $(Y,X)$에 속한 모든 연수의 강수량이 $X$년도의 강수량보다 적어..