그림판유저의 은밀한 개발

백준 2573 - 빙산 이 문제는 빙산을 탐색하고, 빙산 내부의 값을 변경시키고 해당 빙산영역의 개수를 세어주는 문제입니다. 위의 문제에서 요구하는 부분은 두가지입니다. 1. 빙산을 녹인다. (빙산 근처인 상하좌우에 바다가 있는 개수만큼 빙산을 녹입니다.) 2. 빙산의 개수가 2개 이상으로 분리될 경우, 출력한다. 위의 요구하는 부분을 적용시켜 작성한 코드는 다음과 같습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293import ja..

백준 2869 - 달팽이는 올라가고 싶다 달팽이는 낮에 a 미터를 올라가고, 밤에 b미터 떨어집니다. (정상을 도달하는 순간 미끄러지지 않으므로, 끝나게 됩니다.) 이런 문제는 DP를 접근하는 것과 같이 작은 문제부터 생각해야 합니다. 먼저, 달팽이는 하루가 지난 다음날 아래와 같이 이동한 것을 알 수 있습니다. 즉, 1일이 지날 때마다 a - b 만큼을 이동하게 됩니다.일반적으로, 1일에 a - b 만큼을 이동한다는 식을 찾게되면, n * (a - b) >= v 인 n 을 찾으려는 오류를 범하게 됩니다. 여기서 주의할 점은 정상을 도달하는 순간 미끄러지지 않는다는 점입니다. (n + 1)번째의 날에 나무 위에 도달한다고 가정한다면,n 번째 날이 지난 달팽이의 이동거리는 n * (a - b) 이게 되고,..

백준 1799 - 비숍 체스판이 주어졌을 때 비숍은 대각선에 있는 다른 비숍을 잡을 수 있다고 합니다구해야하는 값은 비숍들이 서로를 잡을 수 없도록 하여 체스판 위에 최대로 놓을 수 있는 비숍의 개수를 구하는 문제입니다. N-queen 처럼 백트래킹을 쓰면 쉽게 구현할 수 있을 것 같았지만, 만약 10 x 10 에서 모든 자리가 1로 채워져 모든 자리에 비숍을 놓을 수 있다고 하면 10초안에는 절대로 구할 수 없게됩니다. 따라서 백트래킹을 들어가기 전에 몇가지 경우를 나누어주어야 합니다. 먼저, 체스판을 보게되면 흰색과 검정색으로 나뉘어진 부분을 볼 수 있습니다. (위의 체스판이 아닌 아래의 체스판을 참고해야 합니다.) 검정색 판에 비숍이 놓이게 되면 아래와 같이 흰색 부분에 놓인 비숍은 대각선 위에 위..

백준 10216 - Count Circle Groups 각 적군의 진영에서 Ri 이내 거리에 포함되는 모든 지역을 통신영역으로 가진다면진영의 좌표를 (Xi, Yi)라고 할 때 , 적군의 통신영역은 (Xi, Yi)를 중심으로 하며, Ri를 반지름으로 갖는 원이라는 것을 알 수 있습니다. 이를 통해, 적군의 진영(i, j)끼리 통신이 가능하기 위해서는 통신영역의 중심 즉, 두 진영사이의 거리가 두 Ri, Rj 의 합보다 작아야 한다는 것을 알아야 합니다. 아래 그림을 통해 생각해봅시다. 위의 색칠된 부분이 두 원이 겹치는 부분으로 이 경우에 통신이 가능하다고 하며, 그림을 보면 알 수 있다시피 통신이 가능한 경우는 dist ((Xa, Ya) 와 (Xb, Yb) 의 거리) Ra + Rb 입니다. 두 원사이를 ..

백준 5557 - 1학년 상근이는 덧셈, 뺄셈을 통해 줄 지어진 숫자를 연산하여 가장 마지막 숫자가 나오도록 하고자 한다. 그러나, 연산 도중에 나올 수 있는 숫자는 0이상 20이하라고 한다. 여기서 크기가 21인 배열을 생각할 수 있다. 예시인 "8 3 2 4 8 7 2 4 0 8 8" 을 생각해보자. 처음 8이 올 때, 8이 될 수 있는 경우의 수는 1이다. 8 다음 3이 올 때, 3에서 할 수 있는 연산은 +3, -3 이다. 그 다음 2가 올 때 할 수 있는 연산은 +2, -2 이다. 4가 올 때 할 수 있는 연산은 +4, -4 로 범위를 넘어가면 빼주면 된다. 위의 방식을 코드에 적용하면 다음과 같다. 12345678910111213141516171819202122232425262728293031..