https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 이분탐색 문제 std::unordered_map 쓰면 날로먹을수있을거같이 생겨먹었는데 왠지 모를 이유로 잘 안풀려서 이분탐색으로 해결했다. 둘의 합이 X*10000000 = K 가 되게 해야하기 때문에, 어떤 한 수를 정해줬다면 해당 수와 더해서 K가 되게끔 하는 수를 O(logN) 시간에 찾아야 한다. 찾아내는 가장 좋은 방법은 이분탐색. 이때, 어떤 한 수 a가 한개밖..
boj 1182 부분수열의 합 에서 범위를 두배로 키운 문제. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 밋인더 미들 알고리즘을 사용한다. boj 1182에서와 같이, N이 20일때는 모든 경우에 대해서 브루트포싱할때 전체 연산 횟수가 백만 정도여서 깔끔하게 해결이 가능하지만, N이 40인 이 문제에서는 전체 연산 횟수도 백만의 제곱이어서 시간초과를 받게 된다. 시간초과를 방지하기 위해 입력으로 들어..
https://www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net DP 문제. DP[i] 를 버튼을 i번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값으로 만든다. DP[i] 의 기초 값은 DP[i-1] + 1 이다. ( 1번 버튼 화면에 A를 출력한다를 사용 ) 2, 3, 4번 연산은 사실상 한 세트라고 생각하면 되는데, 어..
https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 굉장히 빠르게 풀어내서 만족스러운 문제. 일단 쉽게 관찰할 수 있는 첫번째 특징으로, 입력으로 들어온 $h_k$ 들의 합 $sum$ 이 반드시 3의 배수여야만 한다. 두 물뿌리개를 동시에 사용하면 물이 3만큼 뿌려지게 되기 때문이다. 예제 입력 4로 설명해주고 있는 또다른 조건의 하나로, 이 조건으로 인해 골드5라는 티어를 배정받지 않았나 싶다. 나무 하나를 2만큼 성장시키는 물뿌리개는 아무리 뿌려도 짝수 높이만큼의 나무를 만들 수 있기 때..
https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net DP 문제. DP[i] 를 i번 색종이를 제일 위에 쌓을때 최대 장수로 정의한다. dp[i]를 구하는 방법은 i번 색종이 밑에 놓일 수 있는 보다 큰 색종이 k에 대한 dp[k] 와 비교를 해서, dp[i] = max(dp[i], dp[k]+1) 식으로 계산해주면 된다. 이때, k를 보다 빨리 찾고 편하게 비교하기 위해서, 입력으로 받는 색종이를 일괄적으로 가로 / 세로로 방향을 고..
https://www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 지문이 이게뭐에요 ㄷㄷ(혼란) 입력으로 들어오는 선분들을 싹 훑으면서(스위핑이다) 진행한다. 현재 이어지고있는 수직선의 구간을 $[s, e]$ 로 저장해 뒀을 때, 새로 입력으로 들어오는 $[x, y]$ 에 대해서 $x > N; for(int i=0; i> a >> b; p.push_back({a,b}); } int ans = 0; int s = p[0].x; int e = p[0].y; for(int i=1; i= p[i].x) e = max(p[..