DAMPER's blog

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 문제 설명 바닥에 쓰여진 방향대로만 움직일 수 있으며, 해당 방향으로 이동했을 때 이루어지는 사이클 또는 집합의 개수를 구하는 문제이다. Union-Find 자료구조를 이용해서 문제를 풀 수 있다. 모든 node를 돌면서 해당 방향으로 움직였을 때의 위치를 이미 방문한 곳이라면 merge()를 통해 병합 후 다른 노드로 이동한다. 처음 방문한 곳이 아니라면 병합..

https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 문제 설명 두 자연수 A, B가 주어졌을 때, A부터 B까지의 수에 대해 2진수로 표현했을 때 1의 개수의 합을 구하는 문제이다. 문제에 따르면, \( f(x) \) 를 다음과 같이 정의할 수 있다. => \( x \)를 이진수로 표현했을 때 1의 개수 문제에서 원하는 값은 다음 식의 결과이다. \( \sum_{x=A}^Bf(x) \) A부터 B까지 모든 자연수에 대한 \..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 문제 설명 중앙(0), 상(1), 하(3), 좌(2), 우(4)로 된 발판이 있다. 두 발이 같은 지점에 있는 것을 불가능하다. 처음에 양발이 모두 중앙에 위치하고, 발을 이동시킬 때마다 cost가 발생한다. 중앙에서 네방향으로 갈 때 = 2 인접한 발판으로 갈 때 = 3 반대편 발판으로 갈때 = 4 그리고 같은 지점을 한번 더 누를 때는 1 cost가 발생한다...

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 문제 설명 이 문제는 두 배열 \( A, B \)의 연속하는 부분배열의 합이 T가 되도록하는 경우의 수를 구하는 문제이다. \( N > T; cin >> n; A.resize(n, 0); for(int i=0;i> A[i]; cin >> m; B.resize(m, 0); for(int i=0;i> B[i]; vecto..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 설명 N개의 별에 대한 (x, y) 좌표가 있다. 이 별들을 직선으로 이어 별자리를 만든다고 한다. 별자리를 만들 때는 다음 조건을 따른다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. ..

www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 처음엔 그냥 naive하게 매번 부분 문자열을 만들어서 비교했더니 역시 시간초과.. O(n^2) 그래서 처음에 'I'를 찾은 다음, 2칸씩 보고 "OI"를 세면서 문자열 P를 찾는다. 이때 본 2칸은 다시보지 않는다. "OI"를 n개 찾으면 결과값 +1, 그리고 찾은 "OI"개수를 1개 빼고 다시 2칸씩 보면서 찾는다. 이런식으로 해결하면 O(n) 으로 해결할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..