Optimal Solution

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 문제 분석 문제의 주인공은 미래의 주가를 예측할 수 있다. 그리고 그 예측이 항상 맞아떨어진다(부럽다). 문제의 주인공 홍준씨는 매일 3가지 중 하나의 행동을 한다고 한다. 주식을 하나 사거나, 원하는 만큼 가진 주식을 팔거나, 아무것도 하지 않는 것이다. 근데 홍준씨는 바보(?)라서 자신이 어떻게 행동을 해야 최대의 이익을 낼 수 있는지는 모른다. 그래서 우리는 홍준씨가 최대의 이익..

https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 분석 N개의 막대 기둥이 일렬로 서 있는데, 이 막대 기둥들을 이용해 양철로 된 지붕을 만든단다. 근데 면적이 가장 작은 창고를 만들고 싶다고 한다. 딱히 특별한 알고리즘을 써서 풀어야 하는게 아니라 단순한 구현 문제이다. 어떻게 문제를 풀어야할까 잠깐 생각을 해봤는데, 은근 단순한 솔루션을 생각해낼 수 있었다. 가장 높이가 높은 막대 기둥을 기준으로, 왼쪽 부분의 넓이 + ..

https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 문제 분석 플레이어가 방을 찾으러 들어가야 한단다. 근데 플레이어의 레벨이 방장의 레벨 +- 10의 범위 안에 있어야 방에 입장할 수 있단다(하긴 뭐 무작정 들어갈 수 있으면 그게 랭크게임인가). 당연하게도 방이 꽉 차면 레벨 조건이 맞아도 들어갈 수 없다. 플레이어가 들어갈 수 있는 방이 없는 경우에는 자신이 직접 방장이 된다. 이런 식으로 해서 플레이어가 주어졌을 때, 여러 방이 생길테고, 어떤 ..

https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 문제 분석 입력으로 주어지는 N과 M은 최대 10^5이다. 만일 하나하나 완전탐색으로 푼다면 O(NM)이 걸릴 것이다. 이는 10^10 ... 이니까 어느 정도일까. 계산기로 쳐보니까 100억 정도에 해당한다. 시간 제한이 1초라서 완전탐색으로 푼다면 시간 초과가 날 것이다. 어떻게 풀어야 시간 내로 풀 수 있을까. 어떤 값을 빠르게 찾아내는 방법. 이분..