목록SWEA (25)
시간이 NullNull
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사이는 우뚝 선 산이 될 수 없음에 주..
048이라는 추억의 게임을 아는가? 2048은 한 때 유명했던 1인용 게임으로, 격자 위에서 숫자가 적힌 타일들을 밀어서 합치고 최종적으로 2048을 만들어 내는 것이 목표인 게임이다. 한번 타일을 밀 때는 상하좌우를 정해서 밀어야 한다. 방향을 정하면 격자 위에 있는 모든 타일이 그 방향으로 밀린다. 만약 어떤 타일이 밀리는 방향에 다른 타일이 있고, 두 타일에 적힌 숫자가 같다면 두 타일은 합쳐져 새로운 하나의 타일이 되고 이 타일에 적힌 숫자는 합쳐진 숫자들의 합이 된다. 이렇게 합쳐져서 만들어진 새로운 타일은 숫자가 같은 다른 타일이 밀려와도 합쳐져서는 안 된다. 만약 같은 숫자가 적힌 타일이 세 개 이상 있을 때는 헷갈리는 경우를 없애기 위해 빨리 벽에 닿게 될 타일을 먼저 민다고 생각한다. 예..
성수는 이제 프로그래밍을 시작하기로 마음 먹은 초보다. 그렇기에 프로그래밍 강좌를 통해 자신의 프로그래밍 실력을 끌어 올리려고 한다. 성수의 실력이 A라고 할 때, 수준이 M인 강좌를 시청하고 나면 성수의 실력은 (A+M)/2가 된다. 즉, 성수는 자신이 보는 강좌가 좋은 지 아닌지 판단하지 않고 그대로 강좌를 받아들이기 때문에, 실력보다 낮은 수준의 강좌를 보면 실력이 낮아질 수 있다. 현재 성수는 아직 아무런 실력이 없다. 즉 실력이 0이다. 성수는 볼 수 있는 강좌 총 N개 찾았고 시간 문제상 이 중에서 K개를 적절한 순서로 선택해 한 번씩 시청하려고 한다. 성수가 같은 강좌를 두 번 이상 보는 일은 없다고 할 때, 성수가 가질 수 있는 실력의 수치는 최대 몇인지 구하는 프로그램을 작성하라. 이 문..
N이 주어질 때, 두 사람이 최선을 다해 게임을 한다면 어떤 사람이 이기게 되는지 출력하는 프로그램을 작성하라. 이 문제에서 가장 힘들었던 점이 최선을 다해 게임을 한다면 이었다. 처음에 모든 경우를 종이에 적어 구해보았는데 숫자가 작은 수부터 시작한다면 경우의 수가 너무 많아지고 계산식이 복잡해 지는 것을 확인하고 역으로 N부터 시작해보았다. 예를 들어 N이 100일때 1. 내가 이기기 위해서는 다음 사람이 무조건 100 "초과" 하는 숫자를 부르게 해야함으로 내가 51 을 부르면 다음 사람은 최소 102를 부르게 되므로 무조건 이길 수 있다. 2. 반대로 그렇다면 나의 상대는 내가 51을 부를 수 없도록 24라는 숫자를 불러 내가 최대 49의 숫자를 부를 수 밖에 없게 만든다. 이 두가지를 반복하게 ..