본문 바로가기

Algorithm283

[BOJ]1509번: 팰린드롬 분할 www.acmicpc.net/problem/1509 JusticeHui님의 풀이(justicehui.github.io/ps/2019/09/21/BOJ1509/)를 참고해서 해결했습니다. 1. 우선 dp를 사용하여 구간 [st, en]이 팰린드롬인지 파악할 수 있습니다. 2. 분할 개수의 최솟값을 구하는 것도 dp를 사용하면 됩니다. dp2[n] = [1, n]구간을 팰린드롬으로 분할하는 최소 개수 라고 정의해보겠습니다. 만약 [j, i] 구간이 팰린드롬이면, [1, j-1]까지 잘 분할하고, [j, i]를 팰린드롬 한 덩어리로 만들어주면 됩니다. 그러므로 dp2[i] = min(dp2[i], dp2[j-1] + 1) 점화식으로 답을 구할 수 있습니다. (단, j 2020. 9. 6.
[BOJ]6588번: 골드바흐의 추측 www.acmicpc.net/problem/6588 jaimemin님의 풀이(jaimemin.tistory.com/895)를 참고해서 해결하였습니다. 핵심은 1. 에라토스테네스 체를 사용하여 Prime Number 구하기 2. N - A_Prime odd number값이 또 다른 B_Prime odd number가 되는 A_Prime odd number 구하기 2번이 가장 핵심이 되는 로직입니다. 1번을 통해 걸러낸 Prime Number 중 홀수값을 대상으로 N - A_Prime odd number = B_Prime odd number 관계가 성립하는 가장 작은 A_Prime odd number를 찾습니다. 그러면 자동으로 A_Prime odd number와 B_Prime odd number가 문제 조.. 2020. 9. 6.
[BOJ]12757번: 전설의 JBNU www.acmicpc.net/problem/12757 오리버거님 풀이(blog.naver.com/PostView.nhn?blogId=uss425&logNo=222033992924&categoryNo=94&parentCategoryNo=63&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView)를 참고하여 해결하였습니다. 주요 기법은 두 가지 입니다. 1. STL map의 lower_bound를 사용 lower_bound는 set이나 map에서 특정 key보다 같거나 큰 key중에 가장 왼쪽에 있는 값을 가져옵니다. upper_bound와의 차이는 특정 key '이상'값을 대상으로 하면 lower_bound 입니다. 특정 key '초과'값을 대상으.. 2020. 9. 6.
[BOJ]11657번: 타임머신 www.acmicpc.net/problem/11657 음의 가중치가 있는 최단 경로 문제입니다. 벨만 포드 알고리즘을 통해 해결할 수 있습니다. 코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ11657.cc 2020. 9. 6.

티스토리툴바