https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 쉬워보였지만, 역시나 나는 나약했다.. 해시맵을 통해 차량 이름과 입장 순서를 매핑한다. 그리고 입장 순서보다 나가는 순서가 빠르면 추월한 것으로 처리했다. 하지만 통과할 수 없었다. 왜냐하면 만약 나가는 순서와 입장 순서가 동일해도 만약 해당 차보다 일찍 들어온 차가 뒤에 있으면 추월한 경우로 간주해야한다. 그래서 이렇게 한 번만 루프를 돌면서 파악하는 것은 어렵다고 판단한 후,..

https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net 어렵지 않은 문제이나 한 부분을 놓치면 틀리기 쉽다. 문제의 조건에서 동명이인이 있을 수 있다는 점에서 multiset을 써야 한다. 그리고 완주한 마라토너를 제거하는데, 이 때 erase() 함수를 쓰면 value에 해당하는 값을 모두 제거한다. 따라서 erase를 쓰지 않고, iterator를 하나 찾아서 이를 제거해야 한다. #include #include using namespac..

https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 드디어 찾았다!!!! 항상 시험에서 마주할 때마다 어렵지는 않은데, 시간을 많이 잡아먹어서 곤란했던 문제이다. 단순한 정렬이 아니라, 여러 조건들에 맞춰서 정렬을 하는 점이 까다롭다. 드디어 스스로 풀긴 풀었는데, 지나치게 코드가 복잡했다. 특히 처음에 입력할 때는 string이 키값이었다가, 나중에 문제를 풀때는 정렬을 위해 빈..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 처음에는 deque 자료구조를 이용해 직접 풀어야 하나 고민했으나, 최대 500,000이라는 요소가 있어서 메모리가 초과될 수 있을 것 같아서 조금 더 효율적인 방법을 고안하기 시작했다. 1부터 16까지 시도해본 결과 정답에 일정한 패턴이 보이기 시작했다. 1 2 2 4 2 4 6 8 2 4 6 8 10 12 14 16 ... 이런 식으로 일정한 구간으로 2씩 증가하는 양상이었다. 해당 구간이 멈..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이의 조건을 자세히 잘 보면 풀기 쉬운 문제이다. 우선 모든 input을 받아놓을 수는 없다. 메모리가 최대 12MB이기 때문에 입력받자마자 바로바로 처리를 해야 한다. 대신 큰 N개의 수만 저장하여 관리하여야 하는데, 이 때 N개 중에서 가장 작은 수를 최대한 빠르게 알아낼 수 있어야 한다. 처음에는 vector에 삽입하고 정렬하기를 반복하려 했다. 하지만 이 경우 최악의 경우 시간복잡도가 O(..

https://www.acmicpc.net/problem/1959 1959번: 달팽이3 첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어지는 횟수를 출력한다. 둘째 줄에 끝나는 점의 좌표를 출력한다. 왼쪽 위 칸의 좌표를 (1, 1), 오른쪽 아래 칸의 좌표를 (M, N)이라고 하자. www.acmicpc.net 처음부터 2차원 배열을 만들어서 구현할 생각은 애시당초 접는다. 지나치게 m, n의 범위가 크기 때문이다. 대신에 상하좌우 이동 제한의 변수를 만들어서 반복적으로 탐색을 하려했는데, 이것도 시간초과가 발생한다. 결국엔 공식을 파악해서 조건문으로 문제를 풀어야 한다. 빠르게 공식을 구하기는 어렵고, 스스로 케이스를 나눠서 공식을 추리해야 한다. #include #include using name..