김머성 블로그

[BAE/<JOON> 문제풀이] 2306. 유전자

https://www.acmicpc.net/problem/2306 2306번: 유전자 DNA 서열은 4개의 문자 {a,c,g,t} 로 이루어진 문자열이다. DNA 서열에는 생명의 신비를 풀 수 있는 많은 정보가 들어 있다. 특히 KOI 유전자의 길이는 사람의 키와 깊은 상관 관계가 있다는 것이 알려 www.acmicpc.net 서론 DP 감 다죽었다. 이걸 3일 동안 코너케이스 찾음;; 풀이 인덱스 i, j 가 유전자 쌍을 이룰 때 i+1 ~ j-1 사이의 가장 긴 유전자 일치 길이에 +2를 해서 저장하면 된다. 추가적으로 독립적인 유전자 쌍 n개가 포함된 경우 길이를 모두 더해줘야 한다. 유전자 쌍의 최소 길이는 2 이므로 추가 인덱스 l ( l : j+1 ~ k-2 ) 을 기준으로 2개의 구간으로 나..

[BAE/<JOON> 문제풀이] 1029. 그림 교환

https://www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 서론 상류층들의 취미용 재테크 미술품 되팔이 ㄷㄷㄷㄷ 그냥 DFS DP 인데 난이도에 비해 티어가 너무 높은 느낌이다. TSP 문제들은 티어 좀 까야하지 않나 싶다. 풀이 단순 DP + DFS 방문이라 딱히 쓸게 없다. DP 배열은 아래와 같다. DP[i][j][k] = i 번째 예술가가 j의 가격으로 k 상태의 방문 배열에서 얻을 수 판매 횟수 점화식은 아래와 같다. DP[i][j][k..

[BAE/<JOON> 문제풀이] 2515. 전시장

https://www.acmicpc.net/problem/2515 2515번: 전시장 첫째 줄에는 그림의 개수 N (1 ≤ N ≤ 300,000)과 판매가능 그림을 정의하는 1이상의 정수 S가 빈칸을 사이에 두고 주어진다. 다음 이어지는 N개의 줄 각각에는 한 그림의 높이와 가격을 나타내는 정 www.acmicpc.net 서론 로직은 맞게 짰는데 이분 탐색 특유의 인덱싱 때문에 맞왜틀을 1시간 넘게 했다. 진짜 개싫다. 솔직히 아직도 틀린 코드가 왜 틀렸는지 모르겠다. 아무리 봐도 로직이 똑같다. 풀이 우선 입력 사이즈를 보면 n log n 이상의 알고리즘을 사용할 수 없다는걸 알 수 있다. 그림을 크기 순으로 정렬하면 다음과 같은 점화식을 세울 수 있다. DP[i] = max(DP[i - 1], DP[..

CodeForces #899 (Div. 2) Write-Up (A ~ D) 작성중.

서론 딱 2년 만에 다시 해본다. 문제 풀이가 너무 감으로 이뤄지고 뭔가 좀 그렇다 싶었는데 끝나고 보니까 모든 문제가 다 그리디였다. 그리디도 진짜 문제 많이 풀어봐야 할 것 같다. 구성적 해 문제도 너무 못 푼다. accepted 글자를 봐도 깔끔하게 풀었다는 느낌을 받을 수가 없다. A/B 2솔딱으로 끝났다.. 특히 B번 난이도는 아직 안적혀서 모르겠는데 시간 이거에 다 뺐다. 인덱스가 복잡하고 자꾸 헷갈려서 적어가며 했어야하는데 이상한 자존심 때문에 암산으로 꾸역꾸역하다가 시간 다 날렸다. 풀이 A. https://codeforces.com/contest/1882/problem/A Problem - A - Codeforces codeforces.com 풀이 주어진 배열과 같은 인덱스에 같은 값이 ..

[BAE/<JOON> 문제풀이] 2613. 숫자 구슬

https://www.acmicpc.net/problem/2613 2613번: 숫자구슬 첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 www.acmicpc.net 서론 파라메트릭. 게다가 판정이 그리디라 더 헷갈림. 근데 파라메트릭 문제들에 DP 태그는 왜 붙어있는지 잘 모르겠다. 풀이 그동안 풀었던 파라메트릭 문제들과 다를건 전혀 없다. 판정 로직이 메인인데 그리디하게 한계 합계까지 더하다가 합계 제한을 초과했을 때 그룹을 생성하고 그 수를 세는 방식이다. 한가지 다른 점은 이 문제는 정해진 그룹의 수를 반드시 만들어야하기 때문에 만약 그룹 수가 ..

[BAE/<JOON> 문제풀이] 2836. 수상 택시

https://www.acmicpc.net/problem/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 서론 스위핑 문제 풀이 상차지와 하차지가 오름차순인 사람들은 따로 거리를 계산할 필요가 없다. 어차피 상근이는 0에서 m까지 가야하므로 가는 길에 다 태워줄 수 있다. 따로 계산해아하는 애들은 상차지와 하차지가 내림차순인 애들이다. 이런 애들은 태우고 내려주고 다시 현재 지점까지 오는데 (상차지 - 하차지) * 2의 추가 이동거리가 발생한다. 이런 추가 거리들만 따로 계산해서 m에서 빼주면 된다..