이 문제는 도저히 모르겠어서 구글링 했다.. 다른 사람들의 풀이를 봐도 도저히 모르겠어서 머리 꽁꽁 싸매고 고민하던 중! 드디어 깨달아버렸다.. 너무 감격한 나머지 흔적을 남기고자 한다. 예를 들어 내가 5457번 채널로 가고 싶다고 하자, 현재 나는 100번 채널을 시청 중이다. | 5457 - 100 | 을 통해 순수 + - 만 이용해 원하는 채널로 가기 위한 횟수를 구한다. 그런 다음 0번 채널부터 1,000,000번 채널까지 반복한다. (인덱스는 i로 설정) 문제에서 주어진 건 500,000이지만 위에서 감소하면서 내려오는 경우도 있으니 1,000,000번까지 고려해준다 i번 채널로 이동 가능하면, i번 채널로 가는데 필요한 버튼 누르는 횟수를 계산하여 반환해주고 i번 채널로 이동 불가능하면 그냥..
문제를 찾아보면 알겠지만 N개의 마을에 사는 N명의 학생들이 특정한 한 집에 모여 파티를 하고, 다시 집으로 돌아가는데 드는 비용 중 최대 비용을 구하는 것이다. 다익스트라 코드는 기본적인 코드이며, 우선 특정한 한 집(코드에서는 x)에서 각각 학생들의 집까지 거리를 구하기 위해 start를 x로 하고 다익스트라를 통해 최소신장트리를 구한다. 그리고 배열 하나를 만들어서 x마을부터 각 학생들의 집(1,2,...,N)까지의 최소거리를 더한다. 다시 for문을 반복하여 각각의 학생들(i번째 학생들)에 대해 다익스트라를 실행 한 뒤, 특정한 집(변수 x)에 도달하기까지 걸리는 최소비용을 구해서 배열에 더해준다. 최소비용중 최대를 구해야하므로 변수 res를 하나 두어 최대를 뽑아낸다. res를 처음에 0으로 초..
시뮬레이션 문제를 풀 땐, 문제에 나와있는 조건대로 잘 따라 풀어주어야 한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 0. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는다. 우선, 만약 벽 또는 자기자신의 몸과 만난다면? break하고 게임을 종료시키면 된다. 그 다음엔 사과가 있는 경우와 없는 경우로 나누어 조건식을 세운 다음 문제를 풀면 된다. 방향 전환이 조금 까다로운데, 문제 처음에..
#include using namespace std; int dp[1000001]; int min(int a, int b) { if (a > b) return b; return a; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; dp[1] = 0; for (int i = 2; i
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 분석 여는 괄호와 닫는 괄호로 이루어진 문자열이 주어지고, 주어진 괄호들의 쌍이 올바른지 확인하는 문제이다. 입력으로는 표준입력을 사용하며, T개의 테스트 데이터로 주어진다. 입력의 첫번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어지고, 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다..
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제분석 N개의 수가 주어지고, 이를 오름차순으로 정렬하는 문제이다. 입력으로는 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력으로는 둘째 줄부터의 입력들을 오름차순으로 정렬하면 된다. 예를 들어, 첫째 줄에 5가 주어지고 두번째 줄부터 차례로 3 6 9 3 6 이 주어졌다고 했을 때, 출력으로..
