[백준/C++] #20366 같이 눈사람 만들래? (Two Pointer)
문제https://www.acmicpc.net/problem/20366구상N개의 눈덩이를 가지고, 4개의 눈덩이를 골라, 2개의 눈사람을 만드는데, 두 눈사람의 높이의 차가 최소가 되도록 하여 최소인 높이 차를 출력하는 문제였다. 지금보면 진짜 바보같지만, 처음에는 진짜 내가 이걸 1초만에 생각해낸게 신기할 정도로 쉬워보이는 풀이 (결과적으로 틀린 풀이) 를 생각해냈다. 무엇이었냐 하면, 눈사람의 지름이 a, b, c, d라 하면, (a+b) - (c+d)의 값이 가장 작으면 되니까, (a-c)-(d-b)의 최소값을 구하면 되겠다 생각해서 눈사람의 지름 오름차순으로 정렬하고, 인접한 배열의 값끼리의 차를 구한 배열을 만들어서, 그걸 또 정렬해서(인덱스 값과 함께 pair로. 인접한것 고르면 안되니까),..
2024. 7. 22.
[백준/C++] #1484 다이어트 (Two Pointer)
문제https://www.acmicpc.net/problem/1484 구상두 제곱수의 차가 G가 되는 경우를 출력하는 문제였다. 제곱수로 이루어진 배열 만들고, 투 포인터로 두 수 찾아서 출력하면 되는 간단한 문제였다. 풀이 + 코드G는 100,000보다 작거나 같은 수이기에 두 제곱수의 차가 100,000보다 큰 최대한 작은 제곱수를 구해보면 대략 51,000 이 나온다. (51,000^2 - 50,999^2 = 101,999) 제곱수로 이루어진 배열 (1^2 ~ 51000^2) 만들고 투 포인터 이용해서 제곱수의 차 구하면 된다. int형의 크기는 4 byte / -2,147,483,648 ~ 2,147,483,647 인데, 51000^2는 2,601,000,000로 int 범위를 넘어섰다. ..
2024. 7. 3.
