공작소

문제 스도쿠는 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 퍼즐을 푸는 방법은 각 가로줄과 세로줄에 1에서 9까지의 숫자를 한 번만 넣고, 3*3칸의 작은 격자에도 1에서 9까지의 숫자를 겹치지 않게 넣어야 한다. 스도쿠를 푸는 방법에는 여러 가지 방법이 있다. 그 중 한가지 방법은 Cross-hatching이다. Cross-hatching방법을 이용할 때는, 먼저 숫자를 하나 골라야 한다. 그런 뒤에, 그 숫자가 등장하는 가로줄이나 세로줄 또는 3*3 박스에 선을 긋는다. 이렇게 선을 그었을 때, 3*3박스에 고른 숫자가 들어갈 수 있는 칸이 한 칸일 때, 그 숫자를 채우는 것이다. 아래 그림 중 왼쪽 그림은 매우 조금만 숫자가 채워진 스도쿠이고, 오른쪽 ..

문제 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. 입력 첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다. 출력 첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다. 제한 2 ≤ N, M ≤ 1,000 0과 1의 개수는 하나 이상이다. 풀이 과정 먼저 이미 있는 1의 모양을 먼저 탐색하면서 방문 기록을 이용해 모..

문제 살아있는 화석이라고 불리는 월곡이는 돈에 찌들려 살아가고 있다. 그에게 있어 수입과 지출을 관리하는 것은 굉장히 중요한 문제이다. 스마트폰에 가계부 어플리케이션을 설치해서 사용하려 했지만, 월곡이는 굉장히 오래 살았기에 원하는 정보를 얻기에는 동작 속도가 너무나도 느렸다. 가끔 입력을 빼먹은 것이 생기면 다시 추가하고 계산하는 것도 느려서, 성격이 급한 월곡이는 결국 스마트폰을 부숴버리고 말았다. 월곡이를 도와주는 프로그램을 작성하기 위해, 아래와 같은 동작들을 처리하는 프로그램을 작성하시오. 작성될 가계부 프로그램은 두 가지 동작을 처리해야 한다. 첫 번째는 월곡이의 생후 p일에 수입/지출 내용을 추가하는 것이다. 수입은 양수, 지출은 음수의 형태로 입력이 들어온다. 두 번째는 월곡이의 생후 p일..

문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 ..

문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다. 루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오. 위의 그림은 루빅스 큐브를 푼 그림이다. 왼..

문제 지훈이가 최근에 즐기는 컴퓨터 게임이 있다. 이 게임은 여러 플레이어가 참여하며, 각 플레이어는 특정한 색과 크기를 가진 자기 공 하나를 조종하여 게임에 참여한다. 각 플레이어의 목표는 자기 공보다 크기가 작고 색이 다른 공을 사로잡아 그 공의 크기만큼의 점수를 얻는 것이다. 그리고 다른 공을 사로잡은 이후에도 본인의 공의 색과 크기는 변하지 않는다. 다음 예제는 네 개의 공이 있다. 편의상 색은 숫자로 표현한다. 공 번호 색 크기 1 1 10 2 3 15 3 1 3 4 4 8 이 경우, 2번 공은 다른 모든 공을 사로잡을 수 있다. 반면, 1번 공은 크기가 더 큰 2번 공과 색이 같은 3번 공은 잡을 수 없으며, 단지 4번 공만 잡을 수 있다. 공들의 색과 크기가 주어졌을 때, 각 플레이어가 사로..