백준(2)
-
백준 2467 - 용액 [C++]
https://www.acmicpc.net/problem/2467 #풀이 입력이 10만개이므로 완전 탐색은 불가능합니다. 그런데 잘 생각해보면 아무 두 용액을 섞었을때 특성값이 양수면 값을 줄여야 0에 가까워지고, 특성값이 음수이면 값을 늘려야 0에 가까워집니다. 따라서, 정렬한 용액 배열에서 첫 인덱스와 마지막 인덱스에 두 개의 포인터를 설정하고, 특성값이 0에 가까워지도록 포인터를 한 칸씩 움직이면서 절댓값이 가장 작은 특성값을 갱신하면 문제에서 요구하는 두 용액을 찾을 수 있습니다. 문제에서 주어지는 배열은 이미 오름차순 정렬이 되어있으므로, 특성값이 양수면 오른쪽 포인터를 1 줄이고, 특성값이 음수이면 왼쪽 포인터를 1 늘립니다. #코드 #include #include #include #inclu..
2024.01.05 -
백준 2630 - 색종이 만들기 [C++]
새해 기념 첫번째 포스팅입니다. 작년 KOI 중등부 첫번째 문제도 비슷했던 것으로 기억이 나는데, 이 문제가 좀 더 쉬웠던 것 같습니다. 문제의 목표는 자른 색종이가 전부 하얀색이거나 파란색이 될때까지 색종이를 반으로 계속 자르고 나서 그 잘라진 하얀색 / 파란색 색종이의 개수를 구하는 것입니다. #풀이 한 변의 길이가 모두 2의 거듭제곱 형태이기 때문에, 좌표를 바꾸고 길이를 계속 절반으로 하는 재귀함수를 구현하면 될 것 같습니다. 구체적으로는, 1. N x N 사이즈의 정사각형 내에 있는 모든 칸의 색을 체크합니다. 2 - 1. 만약 모든 색이 같다면, 해당 색의 색종이 개수에 1을 더해줍니다. 2 - 2. 만약 한 칸이라도 색이 다르다면, N x N 사이즈의 색종이를 위 그림처럼 (N/2) x (N..
2022.01.01