문자열 - 아호 코라식(Aho-Corasick)
아호 코라식(Aho-Corasick)에 대해 알아보자.
[18186 라면사기(large)] https://www.acmicpc.net/problem/18186 .
그리디하게 문제를 해결해보자!
사람들이 많이 푼 다이아 문제 중 하나라서 언젠가 꼭 풀어봐야지 했던 문제다.
좀 보면 그리디라는 건 쉽게 알아차릴 수 있다.
근데 다른사람들도 많이 그랬던데 단순히 3개를 사는 걸 먼저하면 틀린다.
그리디를 어떻게 해야할지가 꽤 까다로운 문제였다.
위에서 얘기 했던대로 라면 사는 걸 7원으로 사는게 가장 이득이니까 단순히 그것부터 하면 틀린다.
대표적인 반례는 B = 3, C = 2일 때 1 2 1 1이 있고 이는 0 1 1 1 로 바꾸고 0 0 0 0으로 바꾸는게 이득이다.
단순히 0 1 0 1로 바꾸면 곤란해진다.
이렇게 되는 이유는 1 2 1 에서 2가 마지막 1보다 크기 때문이다.
이를 어떻게 해결해야 할까?
i+1번째 라면 공장에서 라면을 살때 i-1, i, i+1 중에서 i가 i+1보다 크면, i를 먼저 처리하는 게 중요하다.
근데 사실 i+1번째 공장에서 사야할 라면이 더 많아도 i를 먼저 처리해주면 된다.
그러니 B로 산 행위를 B+C로 바꾸는 걸 먼저해줘도 된다는 뜻이다.
등차수열이니 이렇게 된다.
이게 더 이득인 이유를 대충 말해보면 그 다음 i+2로 가면 B로 따로 사는 것보다 B+C를 B+2C로 바꾸는게 이득이니까 그 가능성을 더 늘리는 것이다.
따라서 아래와 같이 내 구입목록 클래스를 만들었다.
class purchase{
public:
//first = B로 산거 다음에 B+C로 업글
//second = B+C로 산거 다음에 B+2C로 업글
// third = B+2C로 산거.
int first= 0, second= 0, third=0;
ll res = 0;
};
이전에 first 행동을 second행동으로 바꾸는 걸 제일 먼저,
그 다음에 second 행동을 third 행동으로 바꾸는게 두번째,
마지막은 그냥 낱개로 사는 first행동을 하는게 세번째 순으로 i+1번째의 최소 비용을 계산하면 된다.
당연히 메모리와 시간을 주의해야한다.
이전에 샀던 현황으로 이번에 살꺼를 정하는 과정에서 while문을 사용하여 하나씩 처리하면 시간초과고 한번에 계산하면 된다. O(N^2) -> O(N)
small에서는 while문으로 해도 통과했는데 large는 n의 제한이 커지니 당연히 통과하지 않았따.
난 C가 B보다 클때를 고려하지 않아서 한번 틀렸다.
그냥 C가 B보다 크면 C를 B로 바꾸는 문장 하나 넣으니까 맞았다.
나머지 주의 할 점은 코드에 주석으로 처리했다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
class purchase{
public:
//first = B로 산거 다음에 B+C로 업글
//second = B+C로 산거 다음에 B+2C로 업글
// third = B+2C로 산거.
int first= 0, second= 0, third=0;
ll res = 0;
};
int n;
ll B, C;
vector<int> a;
int main(){
fast_io
cin >> n >> B >> C;
C = min(C, B); //C가 B보다 크면 다 B롤 사는게 이득이잖아 ㅋㅋ
a = vector<int> (n+1);
for(int i=1;i<=n;i++) cin >> a[i];
purchase myP[2];
for(int i=1;i<=n;i++){
if (myP[0].first&&a[i]) {
int diff = min(myP[0].first, a[i]);
myP[1].second += diff;
myP[0].res -= 1LL*B*diff;
myP[1].res += (B+C)*diff;
a[i] -= diff;
}
if(myP[0].second&&a[i]) {
int diff = min(myP[0].second, a[i]);
myP[1].third += diff;
myP[0].res -= 1LL*(B+C)*diff;
myP[1].res += 1LL*(B+2*C)*diff;
a[i] -= diff;
}
if (a[i]) {
myP[1].first += a[i];
myP[1].res += 1LL*B*a[i];
a[i] = 0;
}
myP[1].res += myP[0].res;
myP[0] = {0, 0, 0, 0};
swap(myP[0],myP[1]);
}
cout << myP[0].res;
}
아호 코라식(Aho-Corasick)에 대해 알아보자.
docker를 이해해보자
2060 염소줄서기 풀이 및 코드
분할정복을 이용한 다이나믹 프로그래밍 최적화
코드포스 다시 열심히! 블로그도 열심히!
rust 공부시작!
코드포스 블루 달성 후기
여름캠프 및 SUAPC 후기
2023-05-25-Edu Codeforce round 149 (Div.2)
2023-05-13-Edu Codeforce round 148 (Div.2)
HLD(Heavy Light Decomposition)
행렬 거듭 제곱
2023-05-02-It takes two
Codeforce round 868 (Div.2)
2월 11일 문제풀이
Codeforces#846, TypeDB Foreces 2023, Codeforces#848 업솔빙
ps5 게임 : 용과같이 제로 리뷰
백준 23877번 Convoluted Intervals 문제풀이
codeforce round #828(div 3), EDU #137(div 2) 업솔빙
codeforce round #823(div 2), #824(div 2) 업솔빙
AtCoder Beginner Contest 270 업솔빙
ps5 게임 : 용과같이 극 1 리뷰
백준 18719번 Binomal 문제풀이
백준 14288번 회사문화4 문제풀이
백준 3308번 Matching 문제풀이
백준 18186번 라면사기(large) 문제풀이
백준 4196번 도미노 문제풀이
백준 3176번 도로 네트워크 문제풀이
백준 16367번 TV Show Game 문제풀이
ps5 게임 : 페르소나 5 더 로열 리뷰
codeforce round #811(div 3), #812(div 2), CodeTon round 2 업솔빙
백준 21162번 뒤집기 K 문제풀이
codeforce round #808(div 2), #803(div 2, virtual) 업솔빙
codeforce round #807(div 2) 업솔빙
백준 10167번 금광 문제풀이
codeforce round #805(div 3), #806(div 4) 업솔빙
백준 18253번 최단경로와 쿼리 문제풀이
에듀 라운드 131 업솔빙
백준 1949번 우수 마을 문제풀이
백준 3665번 최종 순위 문제풀이
Trie 자료구조 이해하기
merge sort를 이용하여 inversion 개수세기
3솔의 벽이 너무 높다..
lazy propagation없이 구간 갱신하기
코드포스 폭망기념 upsolving
백준 11505 구간 곱 구하기 문제풀이
백준 1305 광고 문제풀이
백준 4386 별자리 만들기 문제풀이
백준 4803 트리
백준 2206 벽 부수고 이동하기 문제풀이
백준 2166 다각형의 면적 문제풀이
백준 12015 가장 긴 증가하는 부분 수열2 문제풀이
백준 10986 나머지합 문제풀이
스택 구현하기 ========== 자료구조의 기본이라고 하면 스택 과 큐가 있다 백준 10828번에서 마주친 스택
매우매우 많은 정렬이 있지만 그중 가장 안 어려운 3가지를 공부해보았다.
Leave a comment