본문 바로가기

전체 글53

백준 1509번 팰린드롬 분할(C) 문제세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다.분할의 개수의 최솟값을 출력하는 프로그램을 작성하시오.입력첫째 줄에 문자열이 주어진다. 이 문자열은 알파벳 대문자로만 이루어져 있고, 최대 길이는 2,500이다.출력첫째 줄에 팰린드롬 분할의 개수의 최솟값을 출력한다.링크https://www.acmicpc.net/problem/1509풀이은근 쉽게 감을 잡을 수 있다.s를 입력받은 문자열이라고 하자. 평범한 dp문제와 같이 dp[n]을 s[1:n]을 쪼갤 때 필요한 최소 팰린드롬 개수로 정의하자. s[n-a:n]이 팰린드롬 문자.. 2024. 8. 29.
Codeforces Round 967 (Div. 2) virtual 풀이 NYPC 본선에서 떨어지고 대학 ps 대회를 대비해서 실력을 늘릴겸 코포 버츄얼을 쳤다. A. Make All Equal (00:04) 최솟값만 존재하게 한다면 풀 수 있어 보여 구현하였고, 예제에서 답이 다르게 나왔다.모든 i에 대해 항상 ai와 같은 값을 가지는 원소만 남게 할 수 있다는 사실을 관찰하였고, 가장 출현하는 빈도가 높은 수를 배열을 통해 구하여 출력하였다. #include #include using namespace std;int a[105];int main(){ int i,t; scanf("%d",&t); while(t--) { int mx = 0,n,cnt=0; scanf("%d",&n); for(i=1;imx)mx=a[b].. 2024. 8. 28.
제1회 한성과고 알고리즘 챌린지 Open Contest 후기 및 풀이 서론 Nypc round2가 끝나고 본선에 갈수도, 못갈수도 있는 상황이라 대학 때를 미리 대비하는 겸 백준에서 open contest가 열리길래 참가하였다. 6시 40분 시작이었는데, 7시 시작인줄 알고 있다가 8분 늦게 시작하게 되었다. A 승강장의 깊이 (예상 난이도 브론즈3) (00:10) 초깃값이 0인 변수 s에 Ai - Bi를 더하고 출력하는 것을 n번 반복하면 되는 단순한 브론즈3 문제이다.예제와 문제의 식만 보고 반쯤 찍듯이 짜서 맞췄다. 소스코드#include int main(){ int i,n,s = 0; scanf("%d",&n); for(i=1;i  B 질문은 계속돼 (예상 난이도 실버3) (00:16) 문제를 보자마자 세그먼트 트리가 생각났다. 세그먼트 트리로 합을.. 2024. 8. 27.
백준 17408번 수열과 쿼리 24(C) 문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오1 i v: Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109)2 l r: l ≤ i  + Aj 중에서 최댓값을 출력한다. (1 ≤ l 수열의 인덱스는 1부터 시작한다.입력첫째 줄에 수열의 크기 N이 주어진다. (2 ≤ N ≤ 100,000)둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)셋째 줄에는 쿼리의 개수 M이 주어진다. (2 ≤ M ≤ 100,000)넷째 줄부터 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.출력2번 쿼리에 대해서 정답을 한 줄에 하나씩 순서대로 출력한다.링크https://www.acmicpc.net/problem/17408풀.. 2024. 8. 26.

티스토리툴바