판교의 메타몽

문제 링크 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 요약 1. 어느 한 숫자의 오른쪽에 위치한 숫자 중, 가장 왼쪽에 위치한 큰 숫자가 해당 숫자의 오큰수가 됩니다. 2. 만약 오큰수가 존재하지 않을 경우, 해당 숫자의 오큰수는 -1이 됩니다. 3. 예시는 다음과 같습니다. ex) 3 5 8 -> (각 숫자의 오큰수의 값) : 5 8 -1 핵심 포인트 다음 문장을 순차적으로 이해하여 하나씩 구현하면 됩니다. 스택을 사용하면 쉽게 풀 수 있습니..

문제 링크 : https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 문제 요약 1. 안전거리는 어느 칸 하나와 가장 가까운 아기 상어와의 거리입니다. 2. 두 칸 사이의 거리는 8방향(대각선 포함)으로 이동하는 최단거리 입니다. 3. 안전거리가 가장 큰 값을 구하세요. 핵심 포인트 안전거리의 뜻을 잘 이해해야합니다. 빈 칸은 무조건 한 개 이상이 주어지므로, 결국 주어진 모든 빈칸에서 가장 가까운 아기 상어와의 거리(=안..

문제 링크 : https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 문제 요약 1. 원숭이는 왼쪽 맨 위칸에서 오른쪽 맨 아래칸으로 최소한의 움직임으로 이동하고 싶습니다. 2. 말의 움직임, 또는 인접한 4방위 움직임을 통해 원숭이는 이동할 수 있습니다. 3. 말의 움직임으로 이동해도, 4방위로 이동해도, 모두 이동 횟수는 1회 입니다. 4. 말의 움직임으로 이동할 경우, 원숭이는 장애물을 뛰어넘을 수 있습니다. 하지만 장애물에 도착..

문제 링크 : https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 이 문제를 푸는 로직은 다음과 같습니다. 1. 기본적으로 죄수1, 죄수2, 상근이가 어느 공통의 문에서 집결할 경우, 탈옥을 했다고 볼 수 있습니다. 때문에 각 구성원들이 문을 딴 횟수를 별도로 저장해서 합산하면 됩니다. 2. 만약 어느 특정한 문에서 3명이 만나게 될 경우, 다음의 값들을 더해주면 됩니다. 상근이가 해당 문까지 도착하기 위해 문을 딴 횟수 + 죄수1이 해당 문까지 도착하기 위해..

문제 링크 : https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 k; for(int i=0; i> v[i]; sort(v.begin(),v.end()); 2. ans의 값은 센서 간의 길이차의 최대값으로 초기화한다. 다음으로 센서간의 거리 차를 gap이라는 vector에 저장해준다. ans = v[v.size()-1]-v[0]; for(int j=1; j=n일 경우, 이는 센서의 갯수보다 집중국의 설치 가능 갯수가 더 많음을 뜻한다. 더 계산하지 않고 for문을 종료하면 된다. 만약 3번을 간과할 경우 Runtime Error (out of bound)가 발생하니 주의하자 4. 정답을 출력한다. #include #include #includ..

문제 링크 : https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 이 문제는 2가지 루트의 최단 거리를 각각 구하여, 그 중 가장 작은 값을 선택하면 된다. 1 -> T1 -> T2 -> N 1 -> T2 -> T1 -> N 이때 경로가 없는 루트일 경우, 적절히 최대 값을 셋팅하여 Stack over flow가 발생하지 않도록 주의해야한다. 문제 풀이는 다음과 같다. 1. 필요한 변수를 선언하고 값을 ..

문제 링크 : https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 풀이는 다음과 같다. 1. 필요한 변수를 선언하고 값을 입력 받는다. 이때 f + 1의 사이즈 만큼 bool문형 배열을 선언한다. int f,s,g,u,d; cin >> f >> s >> g >> u >> d; vector ch(f+1,false); 참고로 bool ch[1000001]로 선언해도 무방하다. 이럴경우 memset이나 별도의 방법을 활용해 배열의 값을 false로 초기화 하는..

문제 링크 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 공통 부모를 찾는 알고리즘이다. 풀이법은 다양하지만 정석대로 Union-Find 알고리즘을 활용했다. 문제 풀이는 다음과 같다. 1. n과 m을 입력 받고 n의 사이즈만큼 공통 조상 배열을 초기화해준다. 또한, n*n의 사이즈만큼 2차원 벡터를 선언한다. 나는 편의상 1부터 계산하기 위해 (n*1)*(n*1)로 선언했다. cin >> n >> m; uni.resize(n + 1); ..

문제 링크 : https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 이 문제는 복잡한 연산 없이 '-' 와 '/'의 사용 횟수 제한만 알고있으면 금방 풀 수 있다. 어떠한 숫자라도 '-'을 사용하면 0이되고, '/'를 사용하면 1이 된다. 때문에 '-'연산과 '/'연산을 사용하는 최대 횟수는 각 1번으로 제한을 두면 된다. 또한 연산 결과가 0과 1일때 발생할 수 있는 문제사항들을 if로 제거해주면 된다. 문제사항들은 다음과 같다. 1*1은 ..

문제 링크 : https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 이 문제는 풀이방법을 친절하게도 문제에 이미 명시를 해뒀다. 첫 번째 그림은 벌 2개가 왼쪽 끝에, 혹은 오른쪽 끝에 몰려있는 케이스를 설명하고 있으며, 두 번째 그림은 벌 하나는 왼쪽(꿀은 맨 오른쪽)이나 오른쪽 끝(꿀은 맨 왼쪽)에 고정, 다른 벌 하나는 그 사이에 존재하는 것을 설명하고 있으며, 세 번째 그림은 벌 2개가 양쪽 끝에 고정되어있고 꿀은 그 사이를 오고가는 것을 설명한다. 문제 풀이는 다음과 같다. 1. 필요한 변수를 선언하고 값을 입력받는다. int n = 0; cin >> n; unsigned long..