BOJ 문제풀이(W26)

15565 귀여운 라이온

인형의 갯수를 누적합으로 구해주고, 투포인터를 이용하여 인형이 K개 이상인 가장 짧은 구간을 찾아주면 됩니다.

이때 투포인터는 end를 하나씩 늘려 가면서 각각의 end를 끝으로 하는 인형이 K개 이상인 가장 짧은 구간을 찾을 수 있습니다.

for (int e = 1; e <= n; e++) {
    while (true) {
      if (sum[e] - sum[s]>=k) s++;
      else break;
    }
    if (sum[e] - sum[s-1]>=k) len = min(len, e-s+1);
 }

찾아준 구간이 정말 K개 이상인 구간인지 보장못함으로 마지막에 값을 갱신할때는 이를 체크해주어야 합니다.

 

다른 풀이로는 구간의 인덱스를 활용하는 풀이가 있습니다.(선생님이 알려주신 풀이입니다)

예전에 풀었던 17844 복붙하기 문제에서 비슷하게 사용했던 테크닉같은데 구현이 아주 짧습니다.

이 풀이에서는...

arr[i] := i번째 라이언 인형의 인덱스

그리고 배열 arr을 K부터 시작해서 끝까지 탐색합니다.

이때 $ans = min(ans, arr_{i} - arr_{i-k+1}+1)$ 이렇게 갱신해줍니다.

마지막으로 이렇게 for문을 끝낸 이후에 가장 짧은 구간을 못찾은 경우 예외처리를 해주면 쉽게 해결 할 수 있습니다.

 

14754 피자박스

N제한이 1,000이라 정말 앞,옆에서 봤을때 상황을 구현해주면 쉽게 해결 할 수 있습니다.

다만 int범위를 넘어 갈 수 있어 주의해야합니다.

 

2671 잠수함 식별

주어진 패턴을 파이썬의 컴파일을 이용하여 미리 만들어두면 더 쉽게 구현 할 수 있습니다.

p = re.compile('100+1+')
p2 = re.compile('01')

dp(i, j) := i~j까지 문자열이 잠수함이면 Ture 아니면 False

위와 같이 배열을 정의합니다.

dp(i, j) = dp(i, k) and dp(k+1, j) 이거나(둘다 True), (k=i+1~j-1) 혹은 i~j까지 문자열이 ="01" 혹은 i~j까지가 주어진 패턴과 일치하면 True

이렇게 점화식을 세워 배열을 채줘주면 됩니다.

주의할 점은 주어진 패턴과 매칭하지만 문자열이 더 긴 경우에도 True가 나올 수 있어 전체 길이가 주어진 패턴과 일치하는지 여부를 확인해주어야 합니다.

if m != None:
	if m.start()+i==i and m.end()+i-1==j:
		f = True

14864 줄서기

그냥 1,2,3,4,5 이런식으로 서있다고 가정을 하고 arr[x]++, arr[y]-- 이렇게 풀었습니다.

inversion counting을 이용한 풀이법은 떠올리지 못했습니다.