Algorithm & Data Structure/백준 알고리즘
오늘은 백준에서 1018번문제 체스판 다시 칠하기를 풀어보았다. MN개의 단위 정사각형으로 나뉜 M X N 크기의 보드가 있다. 정사각형들은 검은색 또는 흰색으로 칠해져있고, 이 보드를 잘라 8 X 8 크기의 체스판으로 만들어야 한다. 변을 공유하는 두개의 사각형은 다른 색으로 칠해져 있는, 즉 체스판은 검은색가 흰색이 번갈아서 칠해져 있어야 한다. 결국 체스판을 색칠하는 경우는 맨 왼쪽 위칸이 흰색 또는 검은색인 경우 두 가지로 나뉜다. 보드는 그런 형식이 지켜져있다는 보장이 없기에 보드를 8 * 8크기의 체스판으로 잘라 몇개의 정사각형을 다시 칠한다. 이 때 다시 칠해야 하는 정사각형의 최소 개수를 구하는 문제이다. N과 M이 첫째 줄에 주어지고 8 fix_cnt : min_fix = fix_cnt ..
달팽이가 막대기를 올라가고 싶단다. 높이가 v 인 나무 막대를 달팽이가 올라가는데 낮에는 a미터 올라가고 밤에는 b미터 미끄러진다. v : 높이 a : 낮에 움직이는 거리 b : 밤에 미끄러지는 거리 d : 올라가는데 걸리는 날 중요한 점은 낮에 올라가면 다시 미끄지지 않기 때문에 먼저 d 를 1 올려주고 v 를 a만큼 먼저 내리고 계산한다. ( a * d ) - ( b * d ) = ( v - a ) ( a - b ) * d = ( v - a ) d = ( v - a ) / ( a - b ) 이다 나머지가 0이라면 ( v - a ) / ( a - b ) + 1 이 답이고 나머지가 있다면 ( v - a ) / ( a - b ) + 2 가 답이다. 코드는 import java.io.BufferedReade..
분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> ... 과 같이 지그재그 순서로 차례대로 1~..번 분수라고 한다. x가 주어졌을 때 x번째 분수를 구하란다. 일단 저 표대로 보려니까 너무 어려워서 그림을 돌려봤다. 피라미드처럼 본다고 그리고 볼 수 있다고 생각하자. 첫번째 라인은 1/1 두번째 라인은 2/1 1/2 세번째 라인은 3/1 2/2 1/3 ... 순서는 1 3 2 4 5 6 .. 이다 여기서 발견한 규칙은 짝수 행은 오른쪽에서 왼쪽, 홀수 행은 왼쪽에서 오른쪽으로 순서가 커지고 행 번호 + 1 = 분모 + 분자, 행의 번호와 그 행의 분수의 숫자는 같다. a : 원하는 분수 번호 cnt : 개수 n : 행 번호 n에 1씩 더할 때 마다 cnt에 n을 더하고..
