전체 글 (128) 썸네일형 리스트형 백준 1118 - 색칠 2 step 1더보기색칠되지 않은 면적을 구하는 것이지만 전체에서 색칠된 영역을 빼는 것으로 생각하고 색칠된 영역의 면적을 구하겠습니다.$K \le 50,c[i] \le 1000$입니다. $K$를 잠시 무시하고 한번만 색칠한다 했을 때 만들어지는 영역들을 생각해 봅시다. 영역의 개수가 최대한 많아지도록 만든다면 다음과 같이 $1001 * 2$개의 영역이 만들어 질 것입니다.각 영역의 경계를 생각해 봅시다. 세로축과 평행한 경계가 4개, 가로축과 평행한 경계가 2002개 만들어 질 것입니다. 이를 세로 경계, 가로 경계라고 하겠습니다. $K$가 50이므로 전부 색칠하면 최악의 경우 세로 경계 200개, 가로경계 100100개가 만들어집니다. 이제 $200 * 100100$로 이 문제를 해결하면 됩니다. ste.. 백준 31749 - 조작 step 1더보기$N$이 홀수일 때는 답이 0입니다.$a_1, a_2$를 조작하여 $a_1$을 $0$으로 만듭니다.$a_2, a_3$를 조작하여 $a_2$을 $0$으로 만듭니다.이런 식으로 $a_{n-1}$까지 $0$으로 만듭니다. 그럼 $a_n$에만 값이 들어있을 것입니다. 이제부터 나머지 숫자들을 $a_n$에 맞출 것입니다.$a_{n-2}, a_{n-1}$을 조작하여 두 숫자를 $a_n$로 만듭니다.$a_{n-4}, a_{n-3}$을 조작하여 두 숫자를 $a_n$로 만듭니다.이런 식으로 $a_1, a_2$까지 조작해서 모든 숫자를 $a_n$으로 만듭니다.step 2더보기위의 3번 과정까지 따라 하면 마찬가지로 $a_n$에만 값이 들어 있습니다. 백준 예제입력에 위 과정을 적용하면 0 0 0 0 0 1.. 백준 31741 - 구간 덮기 step 1 더보기 선분을 1개, 2개, 3개 쓰는 경우에 대해 각각 답을 구하고 그 중 가장 좋은 것을 출력하면 됩니다. 1개를 쓰는 경우 : 전체를 다 덮는 선분이 있어야 합니다. 이 경우 답은 0입니다. 선분들을 (A)시작점을 포함하는 것, (B)시작점과 끝점 사이에 있는 것, (C)끝점을 포함하는 것 3 종류로 나눌 수 있습니다. 지금부터 (C)에서 고른 선분을 $C$, 그 선분의 시작점을 $C_x$, 끝점을 $C_y$ 이런 식으로 쓰겠습니다. 2개 쓰는 경우 : (A)와 (C)의 조합으로 만들 수 있습니다. $C$ 기준으로 $A$를 찾는다고 할 때 (A)에 있는 선분들 중 끝점이 $C_y$보다 큰 선분들 중 끝점이 가장 작은 선분이 최적의 선분입니다. set에 A의 끝 점을 전부 넣어두면 쉽게 .. 이전 1 ··· 37 38 39 40 41 42 43 다음
