BOJ 문제풀이(W23)

7578 공장

구간합을 구하는 문제로 치환되는 순간 매우 편해집니다.

포인트는 문제를 구간합을 구하는 문제로 치환하기와 쿼리에서 요구하는 인덱스를 구하는 부분입니다.

기계가 교차하는 조건을 생각해보면 첫번째 포인트를 잡을 수 있습니다.

$i<j$일때, $a_{i} < a_{j}$이지만 $b_{a_{i}} > b_{a_{j}}$이면 교차합니다.

그러니까 j를 1부터 n까지 돌면서 j~N까지 구간의 합을 구해주면 문제를 해결 할 수 있습니다.

이때 배열을 전부 0으로 초기화시켜주고 j를 하나씩 돌면서 기계를 연결시키면서 배열의 해당 인덱스를 1로 만들어줍니다.

이 부분에서 배열 A의 값이 배열 B의 몇번째 인덱스와 일치하는지를 찾아주는것은 이분탐색을 통해 구현했습니다.

 

2096 내려가기

메모리 제한이 4MB입니다.

N이 10만이라 입력이 30만개인데 int형이 8byte이니, int형 배열은 50만개 정도 선언 가능합니다.

이는 입력만 저장해도 아슬아슬합니다.

따라서 dp배열 크기를 일반적인 경우보다 작게 잡아야합니다.

점화식을 세워보면 dp[i]를 알기 위해선 바로 직전 dp[i-1]만 필요하다는 사실을 알 수 있습니다.

따라서 dp의 크기를 2로 잡아 해결 할 수 있습니다.

 

13548 숨박꼭질3

그래프 탐색문제입니다. 가장 빠른 시간을 찾아주면 됩니다.

dp로도 가능해 보이는데 잘 모르겠습니다.

 

2143 두 배열의 합

N이 1,000이라 두 배열의 부분합은 $O(N^2)$으로 쉽게 구할 수 있습니다.

다만 이렇게 만들어진 배열의 길이가 100만이고 2개가 있어 이를 $O(N^2)$으로 탐색해줄 수 없습니다.

그렇다면 N뒤에 로그하나가 따라오는 정도로 문제를 풀어야하는데 이는 map을 이용하면 쉽게 해결 할 수 있습니다.

A의 부분합 배열을 map에 insert하고 B의 부분합 배열을 전부 보면서 T-B[i]가 map에 있는지 확인해주면 됩니다.