본문 바로가기

런타임 전의 전처리

 (4)
[Python] 1229번 육각수 https://www.acmicpc.net/problem/1229 1229번: 육각수 육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다. 그림 1 그림1은 h1, h2, h3, h4를 의미하며, www.acmicpc.net 23/03/09 조금은 독특한 방식의 DP문제로, 문제에서 주어진 정보를 적극 활용하여 미리 전처리를 해 시간을 대폭 줄여야 하는 문제이다. 만약 문제에서 주어진 정보가 없었더라면 조금은 더 까다로웠을 지 모른다. 이전에 도전했다가 시간초과를 여러 번 받아 실패했던 문제로, 이 글을 통해 도움을 받았으면 좋겠다. 문제 접근 방식: 이 문제는 캡틴 이다솜 문제와 유사한 방..
[Python] 18867번 편지 꼭 해다오 https://www.acmicpc.net/problem/18867 18867번: 편지 꼭 해다오 욱제는 2020년 04월 02일 목요일 14시 00분에 논산 육군훈련소에 입소했다. 욱제는 2020년 04월 29일 수요일에 사회로 돌아온다. 욱제에게 격려의 메세지를 남겨주자. 단, 편지의 내용은 아래의 조건을 www.acmicpc.net 22/11/16 실랜디를 하다가 만나게 된 조금 어처구니없는 문제로, 많이 틀렸었었다. 레이팅이 된 문제이긴 한데, 약간 번외 문제 느낌이 들었어서 흥미롭게 풀었던 기억이 있다. 전형적인 구성적 문제이나, 그 조건이 문자열과 정수론이 결합된 독특한 문제여서 조금 애를 먹었다. 문제 접근 방식: 1바이트 단위로 끊어서 읽는데, 이 $i$번째 문자를 int로 캐스팅 한 값을..
[Python] 1737번 Pibonacci https://www.acmicpc.net/problem/1737 1737번: Pibonacci 첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 22/11/08 신박한 2차원 DP문제로, 처음에는 재귀를 이용한 탑다운 방식으로 접근했었으나, 재귀 시간이 너무 오래 걸려 바텀업 방식으로 전환하여 풀 수 있었던 문제다. 문제 접근 방식: 이 문제를 보면, 기존 피보나치수열의 점화식과는 다르게 아래와 같은 점화식을 가지고 있다. 맨 처음 생각한 풀이는 위의 점화식을 재귀로 구현하고, DP테이블은 딕셔너리로 구현함으로써 하려고 했다. 딕셔너리의 키는 실수 연산을 통해서 구현하려고 했다. 근데, 이..
[Python] 4172번 sqrt log sin https://www.acmicpc.net/problem/4172 4172번: sqrt log sin 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 한 줄에 하나씩 주어진다. 각 줄에는 \(i\)가 주어지며, 이 수는 0보다 작지 않고, 백만보다 크지 않다. 입력의 마지막 줄에는 -1이 주어지며, www.acmicpc.net 22/10/08 DP라고 보기에도 조금 민망할 정도로, 이미 점화식을 문제에서 다 주었다. 이를 메모이제이션 기법을 활용하여 단순 구현만 하면 되는 문제이다. 문제 접근 방식: 처음에는 입력마다 DP값을 구해주도록 했는데, 시간초과가 났다. 그래서 입력 전에 미리 DP값을 다 구해주고(전처리 과정), 입력 할 때마다 그 값을 출력하도록 바꿔주었다. 구현은 math모듈의 floo..

티스토리툴바