김머성 블로그

[BAE/<JOON> 문제풀이] 23085. 판치기

https://www.acmicpc.net/problem/23085 > n >> k; string s; cin >> s; int o = 0, e = 0; vector dp(n + 1, 0); for (int i = 1; i

[BAE/<JOON> 문제풀이] 12929. 빌딩 높이

https://www.acmicpc.net/problem/12929 12929번: 빌딩 높이 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 1,000,000,000) 둘째 줄에는 X와 T의 크기 M이 주어진다. (0 ≤ M ≤ min(N, 500)) M이 0이상일 경우 셋째 줄에는 X[i]가, 넷째 줄에는 T[i]가 주어진다. (1 ≤ X[i] ≤ N, 1 www.acmicpc.net 서론 파라메트릭은 뭘 근거로 이 문제가 파라메트릭이라고 판정을 하는걸까 ? 그냥 앞으로 무슨 문젠지 모르겠으면 파라메트릭으로 상정을 해야겠다. 이 문제는 태그 보고 풀었다. 풀이 빌딩 높이로 파라메트릭 하면 됨. 각 지점마다 빌딩 높이 제한을 설정해야 한다. 모든 지점의 높이 제한을 지키는 빌딩의 최고 높이를 찾는 ..

[BAE/<JOON> 문제풀이] 15483. 최소 편집

https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 서론 이 글 다 쓰고 검색해볼건데 느낌상 99프로 Well-Known 이다. 풀이 LCS 를 구하고 긴 문자열 길이에서 빼는 풀이를 1차적으로 떠올렸지만 문자열 앞뒤를 벗어난 경우 추가 / 제거되는 문자열 길이를 구할 수 없기 때문에 취소했다. 특히 공통 문자열이 중복되는 (aaaaaaa, aaaa) 같은 입력이 주어지는 경우 풀이가 난감해진다. 그래서 그냥 점화식을 새로 구했다. DP[i][j] = 0 ~ i 번째 1번 문자열을 0 ~ j 번째 2번 문자열로 ..

[BAE/<JOON> 문제풀이] 1938. 통나무 옮기기

https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net 서론 정석적인 탐색 문제다. 2020년 카카오 블라인드 7번 문제랑 좀 비슷한 것 같긴 하다. 이게 골드2 문제가 맞나 ? 그래프 태그만 있는 문제들은 티어에 비해 너무 쉽다. 풀이 구현만 잘하면 된다. 통나무 위치는 중간 부분을 기준으로 삼는게 여러모로 편했다. 통나무 4방향으로 옮기고 돌리는 작업 총 5가지 작업을 반복하며 BFS로 탐색하면 된다. 돌릴 때 통나무를 포함..

[BAE/<JOON> 문제풀이] 11967. 불켜기

https://www.acmicpc.net/problem/11967 서론 틀렸습니다. 게시판 반례 전부 동작 확인 후 큰일남을 느낌. 이 후 맞왜틀의 반복. 기적의 반례 발견. 성공.. 풀이 불을 켠 방 수를 세야 한다. 방문한 방 수가 아니라. 문제를 잘 읽지 않으면 여기서 틀린다. 사실 탐색 자체는 매우 간단하다. bfs 하면서 불켜고 불 켠 주변방에 이미 탐색된 방이 있다면 그 방만 다시 탐색하면 된다. 아래와 같은 반례를 회피하기 위해 이러한 로직이 필요하다. 위 그림의 화살표 진행 방향으로 이동했을 때 r1에 도착해서 r2의 불을 켠다면 r2로 가는 경로는 이미 탐색되었으므로 r2에서 켤 수 있는 방은 켜지 못하게되는 불상사가 발생한다. 따라서 어떤 방의 불을 켰다면 그 방의 상하좌우 방을 재탐..

[BAE/<JOON> 문제풀이] 1646. 피이보나치 트리

https://www.acmicpc.net/problem/1646 1646번: 피이보나치 트리 첫째 줄에 N과 시작 위치와 도착 위치가 공백을 사이에 두고 주어진다. N은 50보다 작거나 같은 자연수 또는 0이다. 시작 위치와 도착 위치는 1,000,000,000보다 작거나 같으며, N번째 피이보나치 트리 www.acmicpc.net 서론 구현 연습하자. 경로 구현하는데 너무 헷갈렸다. 태그는 못봤는데 LCA 문젠 것 같다. 풀이 최소 공통 조상을 구하고 출발 정점 s 로부터의 경로와 도착 정점 e까지의 경로를 차례대로 출력하면 된다. ( 전부 U일 수 밖에 없다. ) 그리고 한가지 주의할 점은 n=50 까지 진행했을 때 트리 정점 개수가 상당히 많으므로 미리 정점 번호를 계산해서 s 나 e 가 없는 쪽..