개발기록 개발기록

https://www.acmicpc.net/problem/16951 16951번: 블록 놀이 욱제는 높이가 1인 블록을 매우 많이 가지고 있고, 블록을 쌓아서 탑 N개를 만들었다. 탑은 일렬로 배열했고, 왼쪽에서부터 i번째 탑의 높이는 Ai이다. 욱제가 가장 좋아하는 정수는 K이다. 따라서, 인접한 두 탑의 높이 차이를 K로 만들려고 한다. 즉, Ai+1 - Ai = K를 만족해야 한다. 욱제가 1분 동안 할 수 있는 작업은 탑 하나를 고르고, 탑에 블록을 더 놓아서 높이를 크게 만드는 것 또는 탑에서 블록을 빼서 높이를 작게 만드는 것이다. 인 www.acmicpc.net 완전 탐색 문제입니다. n^2 해도 시간 초과가 나지 않기 때문에 완전 탐색을 할 수 있습니다. 어떤 수를 기준으로 k의 값에 맞추..

https://www.acmicpc.net/problem/16937 16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net 모눈종이의 범위안에서 좌표마다 고려해주는 완전탐색으로 하면 시간초과가 납니다. 스티커는 2개만 붙입니다. 그러므로 스티커를 붙이는 형태를 강제할 수 있습니다. 1, 2 가 각각의 스티커라고 가정했을 때, 1 2 혹은 1 2 이렇게 말이죠. 단, 스티커가 회전하는 것도 고려해야 합니다. #include #include #include using namespace std; struct point { int y, x; }; int n, m, k, res; ..

https://www.acmicpc.net/problem/16638 16638번: 괄호 추가하기 2 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다. www.acmicpc.net 괄호가 가장 우선순위입니다. 그 다음으로 곱셈이 나머지 연산보다 우선순위입니다. 단순히 생각한대로 구현하기만 하면 되는 문제이지만 구현 디테일이 조금 까다로웠던 문제입니다. 저는 괄호만 일괄적으로 계산, 곱셈만 일괄적..

https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]은 등차수열이 아니다. 수열 B = [B1, B2, ..., BN]을 등차수열로 변환하려고 한다. 각각의 수에는 연산을 최대 한 번 적용할 수 있다. 연산은 두 가 www.acmicpc.net 모든 수에 대하여 -1, 0, +1 연산을 적용시켜서 경우의 수를 계산하면 N의 크기가 10^5이기 때문에 시간 초과가 납니다...

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 탐색 문제입니다. 경로를 어떻게 저장할 것이냐가 문제입니다. 경로를 저장하기 위해 dfs를 사용해버리면 시간 초과가 날 것 입니다..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 www.acmicpc.net 기존의 숨바꼭질과 다르게 순간이동의 가중치가 0입니다. 즉, 큐에 들어가있는 가중치가 정렬되어 있지 않습니다. 이것을 해결하기 위..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고 www.acmicpc.net 탐색 문제입니다. 1에서 2까지 도달한다고 합시다. +1, *2 이렇게 두 가지 방법이 있습니다. 즉, 탐색을 해가며 그 지점에 ..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 탐색 문제입니다. bfs로 풀었습니다. 범위 체크와 방문 체크가 필요합니다. #include #include #include using n..