루미 알고리즘

#1111골드부산 관광부산 관광

KOI 2025 1차코딩중등부 2번, 고등부 1번출제 정보올림피아드위원회이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

부산 관광

원제: 부산 관광

문제

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

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

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

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

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

날짜123456789
한국XOOXOOOXO
정올OOXXXOOOX

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

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

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

한국이의 일정을 나타내는 문자열 A=A1A2⋯ANA = A_1 A_2 \cdots A_N와 정올이의 일정을 나타내는 문자열 B=B1B2⋯BNB = B_1 B_2 \cdots B_N가 날짜 ii(1≤i≤N1 \le i \le N)에 대해

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

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

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤2 0001 \le N \le 2\,000
  • 문자열 AA, BB의 길이는 각각 NN이며 모든 문자는 0 또는 1이다.
  • 1≤p1,p3,p5,ppair≤10 0001 \le p_1, p_3, p_5, p_{\text{pair}} \le 10\,000

부분문제

  1. (6점) p1=1p_1 = 1이고, p3=p5=ppair=10 000p_3 = p_5 = p_{\text{pair}} = 10\,000.
  2. (12점) ppair=1p_{\text{pair}} = 1이고, p1=p3=p5=10 000p_1 = p_3 = p_5 = 10\,000.
  3. (16점) 모든 i(1≤i≤N)i(1 \le i \le N) 에 대해 Ai=Bi=1A_i = B_i = 1.
  4. (24점) 모든 i(1≤i≤N)i(1 \le i \le N) 에 대해 Bi=0B_i = 0.
  5. (42점) 추가 제약 조건 없음

입력 형식

첫 번째 줄에 부산에 머무르는 기간을 나타내는 정수 NN이 주어진다.

두 번째 줄에 한국이의 관광 일정을 나타내는 문자열 AA가 주어진다.

세 번째 줄에 정올이의 관광 일정을 나타내는 문자열 BB가 주어진다.

네 번째 줄에 p1p_1, p3p_3, p5p_5, ppairp_{\text{pair}}가 공백을 사이에 두고 주어진다.

출력 형식

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

예제

예제 1

입력
9
011011101
110001110
3 7 12 15
출력
29

예제 2

입력
9
011011101
110001110
1 10000 10000 10000
출력
11

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.