본문 바로가기

PS/BOJ57

백준 9251 / C++ https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [ 풀이 ] dp[i][j]를 문자열 1개를 i번을 볼 것이고 , 나머지를 j번을 보려고 할 때 지금까지 겹치는 것의 개수라고 하자. 겹치지 않으면 한 문자열을 한칸 이동시켜준다. 겹치면 두 문자열을 모두 한칸 이동시켜준다. dp[i][j]=max(dp[i+1][j], dp[i][j+1], if a[i]=b[j], dp[i+1][j+1]+1) 로 쓸 수.. 2022. 7. 21.
백준 10942 / C++ https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net [ 풀이 ] 어떤 문자열이 팰린드롬이라면 양쪽으로 1개씩 옮겨가면서 조사해줄 수 있다. 즉, 이전 상태를 다시 활용할 수 있으므로 메모이제이션이 가능한 문제다. dp[i][j]:= 구간[i,j]가 팰린드롬이면 1, 아니면 0을 의미한다고 하자. 이제 [i-1, j+1]로 이동한다면.. a[i-1]=a[j+1]이고 dp[i][j]=1일때만 dp[i-1][j+1]도 1이 된다. 비트연산으로 간단히 하면 dp[i-1][j+1]=dp[i][j.. 2022. 7. 21.
백준 13975 / C++ https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net [ 풀이 ] 한번 합친 비용은 이후에 계속해서 더해진다. 즉, 처음에 작게 합칠수록 무조건 유리하다. 이제 작은것부터 2개씩 합쳐주면서 그걸 계속 더해나가면 된다. n제한이 1e6이므로 매번 작은걸 2개씩 골라주는건 우선순위큐로 찾아주면 O(logn)에 찾을 수 있다. 이제 구현만 해주면 된다. 최악의 경우 1e10이므로 long long을 써주자. [ 코드 ] #include using na.. 2022. 7. 21.
백준 12099 / C++ https://www.acmicpc.net/problem/12099 12099번: 점심메뉴 Q개의 줄에 줄마다 각 날의 영우와 승관이가 둘 다 좋아하는 메뉴의 수, 즉 u ≤ a ≤ v 이고, x ≤ b ≤ y 인 메뉴의 수를 출력한다 www.acmicpc.net [ 풀이 ] 매운맛, 단맛 수치가 [u,v], [x,y]에 포함되는 메뉴의 개수를 구하는 문제이다. 값이 10억이므로 빠르게 구간 인덱스 판단을 위해 이분탐색을 해야한다. 먼저 값을 매운맛 기준으로 정렬한 후, u보다 크거나 같은 최소 인덱스, v 초과 최소 인덱스를 찾는다. 그 인덱스사이를 순회하며 단맛 또는 [x,y]에 포함되는지 판단해주면 된다. [ 코드 ] #include using namespace std; int n, q, u, v,.. 2022. 7. 15.

티스토리툴바