시간이 NullNull

준환이는 N개의 서로 다른 무게를 가진 무게 추와 양팔저울을 가지고 있다. 모든 무게 추를 양팔저울 위에 올리는 순서는 총 N!가지가 있고, 여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2N * N!가지의 경우가 있다. 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 된다. 예를 들어 무게추가 총 3개, 무게가 각각 1, 2, 4 라고 하면 아래 그림처럼 총 15가지 경우가 나올 수 있다. 이런 방법으로 준환이가 양팔 저울에 모든 무게추를 올리는 방법은 총 몇 가지가 있을까? 이 문제의 경우 앞 문제에서 언급한 DFS에서 static field를 많이 언..

2016년은 삼성전자가 러시아 현지법인을 설립한지 20주년이 된 해이다. 이를 기념해서 당신은 러시아 국기를 만들기로 했다. 먼저 창고에서 오래된 깃발을 꺼내왔다. 이 깃발은 N행 M열로 나뉘어 있고, 각 칸은 흰색, 파란색, 빨간색 중 하나로 칠해져 있다. 당신은 몇 개의 칸에 있는 색을 다시 칠해서 이 깃발을 러시아 국기처럼 만들려고 한다. 다음의 조건을 만족해야 한다. 위에서 몇 줄(한 줄 이상)은 모두 흰색으로 칠해져 있어야 한다. 다음 몇 줄(한 줄 이상)은 모두 파란색으로 칠해져 있어야 한다. 나머지 줄(한 줄 이상)은 모두 빨간색으로 칠해져 있어야 한다. 이렇게 러시아 국기 같은 깃발을 만들기 위해서 새로 칠해야 하는 칸의 개수의 최솟값을 구하여라. 첫 번째 예제이다. 왼쪽에 있는 그림이 입..

의석이는 동서 방향으로 늘어서 있는 산의 N개의 지점에 대한 높이를 측정했다. 서쪽에서 i번째 지점을 i번 지점이라고 하고, 이 지점의 높이는 hi이다. 특이하게도 두 지점이 같은 hi을 가지는 경우는 없었다. 의석이의 친구 상원이가 의석이에게 “우뚝 선 산”이 몇 개인지 찾는 게임을 제안했다. 어떤 두 지점 i,j(1≤i＜j≤N) 사이에 있는 모든 지점을 볼 때, 즉 구간 [i,j]에 대해 이들의 높이의 형태가 “우뚝 선 산”이라는 것을 다음과 같이 정의하기로 했다. 다음을 만족하는 k(i＜k＜j)가 존재해야 한다. i≤l＜k인 모든 l에 대해 hl＜h(l+1)이 성립. k≤l＜j인 모든 l에 대해 hl＞h(l+1)이 성립. 이와 같은 정의에서 두 지점 i와 i+1사이는 우뚝 선 산이 될 수 없음에 주..

N이 주어질 때, 두 사람이 최선을 다해 게임을 한다면 어떤 사람이 이기게 되는지 출력하는 프로그램을 작성하라. 이 문제에서 가장 힘들었던 점이 최선을 다해 게임을 한다면 이었다. 처음에 모든 경우를 종이에 적어 구해보았는데 숫자가 작은 수부터 시작한다면 경우의 수가 너무 많아지고 계산식이 복잡해 지는 것을 확인하고 역으로 N부터 시작해보았다. 예를 들어 N이 100일때 1. 내가 이기기 위해서는 다음 사람이 무조건 100 "초과" 하는 숫자를 부르게 해야함으로 내가 51 을 부르면 다음 사람은 최소 102를 부르게 되므로 무조건 이길 수 있다. 2. 반대로 그렇다면 나의 상대는 내가 51을 부를 수 없도록 24라는 숫자를 불러 내가 최대 49의 숫자를 부를 수 밖에 없게 만든다. 이 두가지를 반복하게 ..