본문 바로가기

백준

 (223)
[ICPC] 백준 14961 - Untangling Chain https://www.acmicpc.net/problem/14961 관찰 같은 방향으로 가는 경우가 없다. 무조건 회전한다. 어쩌면 이를 이용해서 무언가 할 수 있을지도 않을까? 예제 tc 2번을 그려보자. 이처럼 겹치는 부분이 한 번 발생한다. 이를 해결하려면 어떻게 해야 할까? 가장 명확한 방법은 위에서 2만큼 이동하는 부분을 4로 조정하면 된다. 이를 유심히 보자. 밑으로 내려가기 전엔 왼쪽 방향으로 이동을 했었다. 밑으로 내려갈 때 교차가 일어나지 않으려면 왼쪽으로 이동할 때 충분히 이동해야 한다. 얼마만큼? 방문했었던 좌표 중에 가장 작은 x 좌표보다 1 이상 더 이동해야 한다. 이를 일반화 해보자. 이번에 아래 방향으로 이동을 한 상태라면 다음 이동은 왼쪽 또는 오른쪽으로 할 수밖에 없다. 그..
백준 2016 국민대학교 교내 경시대회 풀이 https://www.acmicpc.net/category/detail/1541 2016 국민대학교 교내 경시대회 www.acmicpc.net 그렇다. 현재는 에디토리얼이 제공되고 있지 않으므로 후배로써 풀이를 복원하면 좋을 거 같아 글을 쓴다. PA 13410 거꾸로 구구단 시키는 대로 구구단을 수행하면서 뒤집은 수의 최댓값을 구하면 된다. CPP에서는 std::to_string으로 구구단 결과를 문자열로 바꾼 후 std::reverse로 뒤집고 다시 std::stoi로 전환하는 방법이 있다. 파이썬에서는 역시 str()로 문자열로 바꾼 후 슬라이싱 문법으로 뒤집은 다음 int()로 전환할 수 있다. std 함수의 경우 상수 시간이 크지만 문제에선 제한이 작으므로 문제없이 돌아간다. 전체 코드 - CP..
백준 1498 - 주기문 https://www.acmicpc.net/problem/4354 사전 지식 이 문제를 KMP로 풀고 와야 한다. https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 풀이 문자열 제곱을 제대로 이해하고 왔다면 KMP 실패 함수에 다음 성질이 있음을 알 것이다. 길이 x의 문자열이 주기성을 만족하려면 n - x개의 접미사와 n - x개의 접두사가 같아야 한다. 또한 x|n을 만족해야 한다.(|은 정수론에서 배수관계..
백준 14517 - 팰린드롬 개수 구하기 (Large) https://www.acmicpc.net/problem/14517 풀이 다음 테이블을 세운다. dp(i, j) := i번째 문자부터 j번째 문자까지 해서 부분 수열을 구성했을 때 나올 수 있는 팰린드롬의 갯수 그러면 dp(i, i) = 1, dp(i, i + 1) = 2로 초기화를 할 수 있다. 이 때 입력으로 주어진 문자열 s에 대해 s[i] = s[i + 1]이면 대칭인 팰린드롬이 존재하는 것이므로 dp(i, i + 1) = 3이 된다. 그리고 부분 수열이 가질 수 있는 범위 gap마다 반복문을 돌면서 다음을 더하거나 빼면 된다. 시작점이 i이고 끝점이 j일 때... dp(i + 1, j)에서 그대로 가져오는 경우 -> dp(i, j)에서 단순히 확장한 것으로 간주할 수 있다. dp(i, j - 1..
[ICPC] 백준 14959 - Slot Machines https://www.acmicpc.net/problem/14959 사전 지식 이 문제를 제대로 푸려면 다음 두 문제를 먼저 풀고 올 필요가 있다. https://www.acmicpc.net/problem/16570 16570번: 앞뒤가 맞는 수열 수열 (a1, a2, ⋯, aN) 이 다음의 성질을 가지면 그 수열은 k-앞뒤수열 이라고 한다. (a1, a2, ⋯, ak) = (aN-k+1, aN-k+2, ⋯ , aN), 1 ≤ k < N 어떤 수열이 k-앞뒤수열일 때, k의 최댓값 k*를 그 수열의 앞뒤계 www.acmicpc.net https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다...

티스토리툴바