RiseOJ – 부산 관광

설명

부산광역시는 관광객의 교통 이용 편의를 위하여 다음 네 종류의 교통 티켓을 판매한다.

구분	사용 인원	유효 기간	가격	비고
1일권	$$1$$ 명	구매한 날 당일 1일	$$p_1$$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
3일권	$$1$$ 명	구매한 날을 포함한 연속 3일	$$p_3$$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
5일권	$$1$$ 명	구매한 날을 포함한 연속 5일	$$p_5$$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
묶음권	$$2$$ 명	구매한 날을 포함한 연속 4일	$p_{\text{pair}}$	유효 기간 내에 두 사람 모두 교통 이용 가능

모든 티켓은 구매 즉시 효력이 발생하며, 표에 명시된 기간 동안 매일 교통을 이용할 수 있다. 물론, 티켓을 보유하고 있는 채로 교통을 이용하지 않아도 되고, 유효한 티켓을 동시에 여러 장 보유해도 되고, 티켓의 유효 기간이 $$N$$ 일간의 관광 일정 이후에 끝나도 무방하다. 그리고
$$p_1 \leq p_3 \leq p_5$$ 가 항상 성립하는 것은 아님에 유의하라.

한국이와 정올이는 부산에서 $$N$$ 일간 같이 머무른다. 하지만, 둘은 각각 자신만의 관광 일정을 세워두어 각 날마다 자신이 관광을 진행할지의 여부를 결정해 두었다. 관광 일정을 소화하기 위해서는 두 사람 모두 관광을 진행하는 날마다 적어도 한 장의 유효한 티켓(묶음권 포함)을 보유해야 한다.

예를 들어, $$N = 9$$ 이고, $$p_1 = 3$$ , $$p_3 = 7$$ , $$p_5 = 12$$ , $p_{\text{pair}} = 15$ 이고, 한국이와 정올이 각각의 일정이 아래와 같은 경우를 고려해 보자.

날짜	$$1$$	$$2$$	$$3$$	$$4$$	$$5$$	$$6$$	$$7$$	$$8$$	$$9$$
한국	$$X$$	$$O$$	$$O$$	$$X$$	$$O$$	$$O$$	$$O$$	$$X$$	$$O$$
정올	$$O$$	$$O$$	$$X$$	$$X$$	$$X$$	$$O$$	$$O$$	$$O$$	$$X$$

1일권만 사용하면 총 $$11$$ (관광 일수) $\times$ $$3$$ (1일권 가격) $$= 33$$ 의 비용이 든다.

하지만, 만약 두 사람이 5일차-8일차 동안 묶음권 $$1$$ 장을 공유하면 총 $$30$$ 의 비용만 소모된다.

심지어 한국이가 5일차-7일차, 정올이는 6일차-8일차를 각각 3일권으로 구입하면 총 비용이
$$29$$ 로 더 절약된다.

한국이의 일정을 나타내는 문자열 $A = A_1 A_2 \cdots A_N$ 와 정올이의 일정을 나타내는 문자열 $B = B_1 B_2 \cdots B_N$ 가 날짜 $$i$$ ( $$1 \leq i \leq N$$ )에 대해

한국이가 관광을 진행하면 $$A_i = 1$$ , 아니면 $$A_i = 0$$
정올이가 관광을 진행하면 $$B_i = 1$$ , 아니면 $$B_i = 0$$

의 형태로 주어질 때, 두 사람 모두 관광을 진행하는 날마다 적어도 한 장의 유효한 교통 티켓(묶음권 포함)을 보유하도록 하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하라.

제약

주어지는 모든 수는 정수이다.
$1 ≤ N ≤ 2\, 000$
문자열 $$A$$ , $$B$$ 의 길이는 각각 $$N$$ 이며 모든 문자는 0 또는 1이다.
$1 ≤ p_1 , p_3 , p_5 , p_{\text{pair}} ≤ 10\, 000$

입력 형식

첫 번째 줄에 부산에 머무르는 기간을 나타내는 정수 $$N$$ 이 주어진다.
두 번째 줄에 한국이의 관광 일정을 나타내는 문자열 $$A$$ 가 주어진다.
세 번째 줄에 정올이의 관광 일정을 나타내는 문자열 $$B$$ 가 주어진다.
네 번째 줄에 $p_1 , p_3 , p_5 , p_{\text{pair}}$ 가 공백을 사이에 두고 주어진다.

출력 형식

첫 번째 줄에 최소 비용을 나타내는 정수를 출력한다.

서브태스크

서브태스크	점수	설명
1	6점	$$p_1 = 1$$ 이고, $p_3 = p_5 = p_{\text{pair}} = 10\, 000$ .
2	12점	$p_{\text{pair}} = 1$ 이고, $p_1 = p_3 = p_5 = 10\, 000$ .
3	16점	모든 $$i$$ ( $$1 \leq i \leq N$$ )에 대해 $$A_i = B_i = 1$$ .
4	24점	모든 $$i$$ ( $$1 \leq i \leq N$$ )에 대해 $$B_i = 0$$ .
5	42점	추가 제약 조건 없음

예제 1

입력

출력

예제 2

입력

9
011011101
110001110
1 10000 10000 10000

출력

문제 정보

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2025 > 1차 대회 > 중등부 2번 / 고등부 1번

올림피아드 > 한국정보올림피아드 > KOI 2025 > 1차 대회 > 중등부 올림피아드 > 한국정보올림피아드 > KOI 2025 > 1차 대회 > 고등부

태그

#DP JudgeKOI

날짜	$\(1\)$	$\(2\)$	$\(3\)$	$\(4\)$	$\(5\)$	$\(6\)$	$\(7\)$	$\(8\)$	$\(9\)$
한국	$\(X\)$	$\(O\)$	$\(O\)$	$\(X\)$	$\(O\)$	$\(O\)$	$\(O\)$	$\(X\)$	$\(O\)$
정올	$\(O\)$	$\(O\)$	$\(X\)$	$\(X\)$	$\(X\)$	$\(O\)$	$\(O\)$	$\(O\)$	$\(X\)$

부산 관광

평가 및 의견

풀이 제출

구분	사용 인원	유효 기간	가격	비고
1일권	$\(1\)$ 명	구매한 날 당일 1일	$\(p_1\)$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
3일권	$\(1\)$ 명	구매한 날을 포함한 연속 3일	$\(p_3\)$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
5일권	$\(1\)$ 명	구매한 날을 포함한 연속 5일	$\(p_5\)$	유효 기간 내에 구매한 사람 본인만 교통 이용 가능
묶음권	$\(2\)$ 명	구매한 날을 포함한 연속 4일	$p_{\text{pair}}$	유효 기간 내에 두 사람 모두 교통 이용 가능

서브태스크	점수	설명
1	6점	$\(p_1 = 1\)$ 이고, $p_3 = p_5 = p_{\text{pair}} = 10\, 000$ .
2	12점	$p_{\text{pair}} = 1$ 이고, $p_1 = p_3 = p_5 = 10\, 000$ .
3	16점	모든 $\(i\)$ ( $\(1 \leq i \leq N\)$ )에 대해 $\(A_i = B_i = 1\)$ .
4	24점	모든 $\(i\)$ ( $\(1 \leq i \leq N\)$ )에 대해 $\(B_i = 0\)$ .
5	42점	추가 제약 조건 없음