Dior2ky의 it's IT

백준 14889번 스타트와 링크 문제이다. 이번 문제는 설명이 매우 길다. 사람을 두 그룹으로 나누어 묶고 시너지 표를 보고 각 그룹의 시너지의 차이를 구하면 된다. 이해가 잘 안된다면 입출력 예시를 본다. 이번 문제도 백트래킹 문제이기 때문에 한 그룹에 사람을 한명씩 넣어가도록 한다. 한 그룹에 사람이 반절 차게 되면 다른 한 그룹도 정해지게 된다. 그룹이 정해지는 순간 시너지 표에서 각 그룹의 시너지 합을 구해 차를 비교해준다. 차가 최솟값이 되어야 하기 때문에 최솟값으로 구해진 값과 비교하여 갱신해준다. 여기서 생각해줘야 할 점은 solve 함수에 들어간 k값이다. k 값을 넣음으로써 그룹에 한 사람이 들어갔다면 다시 처음사람부터 확인하는 것이 아니라 k번째 다음 사람부터 확인이 가능하다. def ..

백준 15652번 N과 M (4) 문제이다. 역시 N과 M 문제이다. 단계별로 풀어보기 백트래킹 항목에 있는 마지막 N과 M 문제이다. (다른 N과 M 문제들은 더 있다...) 이번에는 비 내림차순이라고 한다. 다른말로 하면 오름차순에 중복까지 가능하다고 생각하면 된다. 역시 백트래킹 문제이므로 비슷하게 풀어준다. N과 M (2) 문제와 비교하면 편할 것 같다. (2) 문제에서는 숫자 하나를 사용하면 그 숫자까지의 check 배열을 증가 시켰지만, 이번에는 그 숫자가 중복이 가능하므로 그 숫자 하나 아래 값 까지만 check 배열의 값을 증가시킨다. 이번 문제는 ruby 언어를 사용하였다. def func(cnt) if cnt == $m for i in 0...$m print $arr1[$arr2[i]]..

백준 1018번 체스판 다시 칠하기 문제이다. 문제는 다음과 같다. M*N의 색깔이 칠해진 판이 주어지고 해당 판에서 8*8의 구간을 골라 체스판을 만드는데 체스판은 흰색과 검정색이 번갈아 나오는 체스판을 만들어야 한다. 가장 적게 칠해서 체스판을 만드는 경우 몇번만 칠하면 되는지를 구하는 문제이다. 브루트포스 유형의 문제이기 때문에 하나하나 확인해 보도록 한다. 체스판은 8*8의 크기이고 해당 크기로 주어진 판에서 자를 수 있는 모든 경우를 확인해보자 언어는 ruby를 사용하여 프로그래밍 하였다. def find1(arr, m, n) result = 64 for i in 0...m-7 for j in 0...n-7 count = 0 for k in 0...8 a = k % 2 for l in 0...8..

백준 11729번 재귀로 유명한 하노이의 탑 문제이다. 문제는 다음과 같다. 일반적인 하노이의 탑 문제이다. 입력값과 출력값, 예제가 주어져 있다. 출력은 총 움직인 횟수를 먼저 출력하고 움직임을 하나씩 출력하도록 되어있다. 언어는 ruby를 사용하여 프로그래밍 하였다. def move(n,st,en,si) if n == 2 puts "%d %d" %[st, si] puts "%d %d" %[st, en] puts "%d %d" %[si, en] return end move(n-1, st, si, en) puts "%d %d" %[st, en] move(n-1, si, en, st) end a = gets() a = a.to_i sum = 1 for i in 0...a-1 sum = sum * 2 + 1..