https://www.acmicpc.net/problem/2470 1. 서론 https://coding-log.tistory.com/267 [JAVA] 백준 2470 두 용액https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어coding-log.tistory.com 이 문제는 예전에 투 포인터로 푼 적이 있는 문제이다. 하지만 이분 탐색을 공부하기 위해서 이분 탐색으로 풀어봤다.예시를 보면 대강 맞는 것 같은데 1%에 틀려서 다른 풀이들도 보고 GPT한테 코드 좀 고쳐달라고 했는데 어쨌든 혼자서 풀지 못한 문제이..

https://www.acmicpc.net/problem/19951 1. 서론 이 문제는 누적합 유형의 문제이다. 그런데 문제는 일반적으로 누적해서 합을 구한 후 그를 응용하는 일반적인 누적합 문제가 아니다.나는 GPT에게 이 문제를 어떻게 누적합으로 푸는 거냐고 물어봤고 GPT는 '차분배열'을 이용하면 된다고 했다.아마... 혼자서는 못 풀었을 듯. 이렇게 하나 배웠으니 뿌듯합니다.   2. 문제 풀이 n개의 칸이 있고, 특정 구간을 뜻하는 a, b가 m번 주어진다. n개의 칸에서 a~b 구간만 k만큼 값을 더해준 값을 구하는 것이 문제다.문제는 이 n, m의 범위가 100,000 이라는 것이다. 즉, 그냥 단순히 반복문을 이용해 구간만큼 값을 돌려준다면 시간초과가 나게 되는 문제인 것이다. 처음에는 ..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 서론 투 포인터 문제이다. 투 포인터의 개념은 알겠으나 문제만 보면 어떻게 응용해야 할지 모르겠어서 일부러 고른 문제이다. 덕분에 새로운 응용 방법을 배우게 된 효자 문제. 2. 문제 풀이 엄청나게 길게 써있지만 결국엔 그냥 배열에 있는 값 중 두 개를 골랐을 때 그 답이 0이거나 0에 가장 가까운 두 값을 출력하는 것이 문제이다. 그리고 이 모든 것에 해당..

https://www.acmicpc.net/problem/13699 13699번: 점화식다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ nwww.acmicpc.net 1. 서론 실버 4인데... 두 가지 고비가 있었던 문제다. 첫 번째: 점화식 구현. 두 번째: 자료형. DP 유형이라 실 4 임에도... 쉽지 않았다는 ㅜㅜ 2. 문제 풀이 문제에서 대놓고 식을 준다. 식을 보고서는 DP로 구현하는구나 깨닫게 된다.. ..

https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 1. 서론 되게 전형적이고 별로 어렵지도 않은 투 포인터 문제인데 더럽게 오래 걸린 문제이다. (다 소인이 부족한 탓입죠, 예) 2. 문제 풀이 N개의 수열이 주어진다. 그 연속된 수열 중 (순서 바꾸기 금지) 같은 값이 k개 보다 많으면 연속 수열이 끊긴다. 주어진 수열에서 이 연속 수열의 최댓값을 구하는 문제이다. ex) 9 2 3 2 5 5 6 4 4 5 7 3 2 5 5 6 4 4 =..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 1. 서론 골3 치고는 어렵지 않은, 그러나 오히려 커다란 교훈을 준 문제이다. 근데 이 문제가 나에게 쉬웠던 이유는 예전에 이와 비슷한 문제를 푼 경험이 있기 때문이다. swea 문제였던 것 같은데 블로그에는 없는데 어쨌든 풀어 본 경험이 날 도와줬다. 2. 문제 풀이 여러 대륙이 주어지고 그 대륙들은 모두 처음에는 떨어져 있다고 가정한다. 그랬을 때 대륙간을 연결하는 최솟값을 구하는 게 이 문제이다..