PS
BOJ 17298 - 오큰수
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 N 의 최대 크기가 백만이기 때문에, 단순히 이중 포문을 쓰면 당연히 시간초과가 발생한다 그래서, 처음에 N 개의 수들을 벡터에 저장해 둔 뒤, 스택을 이용해서 풀어야 한다 (사실 스택을 쓰는것을, 문제에서 주는 힌트를 보고 스택써야겠구나 생각했다) 스택에는, N개의 수가 들어가는게 아니라, N개의 수가 위치한 인덱스 값을 넣는다 비어있는 상태의 스택에서는, 즉 첫번째 인덱스는 반드시 들어가고 스택이 비어있지 않은 상태에서는..
BOJ 2075 - N번째 큰 수
www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 메모리 제한이 있는 문제여서 단순히 이차원배열이나 벡터를 쓰면 메모리 초과가 발생한다. 이 문제를 풀기위한 핵심 아이디어는, 입력받은 모든 값을 메모리에 저장하는게 아니라, 최소힙을 이용해서 N 개 만큼만 받은뒤, N 개 이상의 입력이 들어오는 경우, 최소힙에 담긴 가장 작은 값과 비교해서 더 크면 추가해주는 방식으로 쭉 배열을 돌리면 결국 N 개만 최소힙에 남게되고, 가장 큰 것 ~ N번째로 큰 것 만 최소힙에 남게..
BOJ 9328 - 열쇠
www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 이 문제는 BFS 를 이용해서, 얻을 수 있는 문서의 최댓값을 찾아야 하는 문제다. 다른 BFS 기본 문제들 처럼 단순히 BFS 로 탐색해서는 풀 수 없다. 이 문제를 풀기위한 가장 핵심이 되는 아이디어는 열쇠를 발견하고 나서, 해당 열쇠와 일치하는 문에 가서 문을 여는게 아니라, 열쇠를 발견하면 이 열쇠와 일치하는 문을 미리 열어놓고, BFS 를 수행한다는게 핵심이다. 처음에 입력받을때, 일부 열쇠를 얻고 시작하면, 그 ..
BOJ 1918 - 후위 표기식
www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 전형적인 스택 문제다 입력값에 따른 케이스를 잘 분류해서 연산하면 답이 나온다 - c++ #include #include #include using namespace std; stack st; string input, answer; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> input; for (int i = 0; i
BOJ 1043 - 거짓말
www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 처음에 문제 풀때, 진실을 아는 사람의 정보를 담는 배열, 파티를 구성하는 2차원 배열로 문제를 해결하려 했으나, 이전 차례 혹은 다음 차례의 파티에서 진실을 알게 될 경우를 계산하지 못해서 틀렸다 더보기 #include #define MAX 51 using namespace std; int N, M; bool known[MAX]; // 진실을 아는 사람들 bool arr[MAX][MAX]; // i 번 파티의 참가자 j..
BOJ 15961 - 회전 초밥
www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 먼저 일반 배열을 사용해서 원형 초밥에 담긴 초밥 정보들을 저장하게 한다 원형 큐 대신에 배열을 사용할 수 있는것은 모듈러 연산을 적절히 잘 수행하면 마치 원형 큐 처럼 순회가 가능하기 때문이다. (아래 코드에서 arr[(i + k - 1) % n]) 그 다음 k 개 연속으로 먹을수 있는 경우에 대해서 가짓수를 센다. 다음으로 n 만큼 반복문을 돌리면서, 제일 먼저,..
BOJ 16681 - 등산
www.acmicpc.net/problem/16681 16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 이 문제는 다익스트라 알고리즘을 사용해야 한다. 이 문제의 특징은 시작지점(집) 에서 도착지점(고려대) 로 가는 최단거리를 바로 구하는게 아니라, 어떤 임의의 지점을 선정해서 그 지점을 거치고 도착지로 가야한다 먼저, 시작지점에서 어떤 임의의 지점까지는 항상 높이가 증가하는 방향으로 진행해야한다. 그리고 해당 지점에 도착하고 나면, 도착지점까지 가야하는데, 도착지점까지의 높이가 항상 감소하는 방향으로만..
BOJ 1941 - 소문난 칠공주
www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 이 문제는 백트래킹을 이용해야 풀 수 있는 문제이다. 총 25명의 학생중 7명을 조합으로 추려낼 수 있게 해주고, 7명을 뽑아냈다면, 그 7명 중에서 4명 이상이 이다솜파인지 확인해야하며, 동시에 그 7명이 인접해 있는지 확인해야 한다. 이 모든 조건을 만족한다면 경우의 수를 하나씩 세서 답을 구한다. - c++ #include using namespace std; int answer; int dy[4] = {-1..