STUDY

페그 솔리테어 문제 페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다. 핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다. 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 1 ≤ N ≤ 100이 주어진다. 각 테스트 케이스는 게임판의 초기 상태이다. 게임판은 모두 같은 모양을 가진다. (예제 참고) '.'는 빈 칸, 'o'는 핀이 꽂혀있는 칸, '#'..

혼자 하는 윷놀이 문제 오전 4시, 민재는 윷놀이를 하고 싶어졌다. 하지만 다들 자는 시간이라 윷놀이를 같이 할 사람은 없었다. 민재는 윷놀이를 혼자 할 수 있는 방법을 생각해냈다. 혼자 하는 윷놀이에 적용되는 규칙은 다음과 같다. 처음에 말은 윷판의 오른쪽 아래에 위치한다. 열 번의 차례 안에 말 하나가 완주하면 민재가 승리한다. 차례 한 번에는 윷가락 네 개를 던진 후: 뒷면이 하나인 경우 말을 한 칸 전진시킨다. 뒷면이 둘인 경우 말을 두 칸 전진시킨다. 뒷면이 셋인 경우 말을 세 칸 전진시킨다. 모두 뒷면인 경우 말을 네 칸 전진시킨 뒤, 윷을 추가로 던진다. 모두 앞면인 경우 말을 다섯 칸 전진시킨 뒤, 윷을 추가로 던진다. 윷판을 정해진 경로로 한 바퀴를 돌아 윷판의 오른쪽 아래에 도착한 뒤 ..

화산쇄설류 문제 화산학자 윤재상은 어느 화산섬을 탐사하러 갔다가 곧 섬에 있는 화산들이 곧 폭발하기 시작할 것이라는 급보와 각 화산의 폭발 시점 정보를 받았다. 섬은 M행 N열의 행렬로 표현된다. 어떤 화산의 위치를 (x, y), 폭발을 시작한 시각을 t 라고 하자. t+δ 시각이 되면 δ ≥ |u-x|+|v-y|인 모든 (u, v)위치의 지대들은 높이 무관하게 화산쇄설류가 덮치게 된다. 재상인 빨리 탈출을 하고싶다. 재상이는 처음에 X행 Y열에 있다. 재상이는 단위 시간 당 상하좌우 한 칸만 움직일 수 있다. 재상이는 화산이 있는 위치와 화산쇄설류가 뒤덮인 곳은 갈 수 없다. 재상이는 화산쇄설류를 피해서 되도록 가장 높은 곳으로 피하고 싶고, 되도록 가장 빨리 도달하기를 원한다. 재상이가 화산쇄설류를 ..

중국 신분증 번호 https://www.acmicpc.net/problem/16196 16196번: 중국 신분증 번호 첫째 줄에 신분증 번호가 주어진다. 신분증 번호는 18자리이고, 처음 17자리는 0부터 9까지 숫자로만 이루어져 있다. 마지막 1자리는 0부터 9까지 숫자이거나 'X'이다. 둘째 줄에는 올바른 지역 코 www.acmicpc.net 문제 중국의 시민은 모두 신분증 번호를 가지고 있다. 신분증 번호는 18자리이다. 처음 17자리는 숫자이고, 마지막 1자리는 숫자이거나 'X'이다. 처음 17자리는 3개의 연속된 부분으로 나누어져 있다. 각각의 부분은 차례대로 지역 코드, 생일 코드, 순서 코드를 의미한다. 지역 코드는 6자리이다. 올바른 지역 코드는 정부에 의해 미리 정해져 있으며, 여기에 포..

봄버맨 2 문제 봄버맨은 크기가 R×C인 직사각형 격자판 위에서 살고 있다. 격자의 각 칸은 비어있거나 폭탄이 들어있다. 폭탄이 있는 칸은 3초가 지난 후에 폭발하고, 폭탄이 폭발한 이후에는 폭탄이 있던 칸이 파괴되어 빈 칸이 되며, 인접한 네 칸도 함께 파괴된다. 즉, 폭탄이 있던 칸이 (i, j)인 경우에 (i+1, j), (i-1, j), (i, j+1), (i, j-1)도 함께 파괴된다. 만약, 폭탄이 폭발했을 때, 인접한 칸에 폭탄이 있는 경우에는 인접한 폭탄은 폭발 없이 파괴된다. 따라서, 연쇄 반응은 없다. 봄버맨은 폭탄에 면역력을 가지고 있어서, 격자판의 모든 칸을 자유롭게 이동할 수 있다. 봄버맨은 다음과 같이 행동한다. 가장 처음에 봄버맨은 일부 칸에 폭탄을 설치해 놓는다. 모든 폭탄이..

인내의 도미노 장인 호석 문제 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 공격과 수비를 하는 게임이다. 공격수는 도미노를 계속 넘어뜨리고 수비수는 도미노를 계속 세우려고 한다. 본 게임은 다음과 같이 진행된다. N 행 M 열의 2차원 격자 모양의 게임판의 각 격자에 도미노를 세운다. 각 도미노는 1 이상 5 이하의 높이를 가진다. 매 라운드는 공격수가 먼저 공격하고, 수비수는 공격이 끝난 뒤에 수비를 한다. 공격수는 특정 격자에 놓인 도미노를 동, 서, 남, 북 중 원하는 방향으로 넘어뜨린다. 길이가 K인 도미노가 특정 방향으로 넘어진다면, 그 방향으로 K-..

삼각형 게임 문제 삼각형 게임은 시작할때 여섯개의삼각형을 부여받는데, 각 변에는 숫자가 쓰여있다(그림 참고). 이 삼각형들을 돌리고 움직여서 육각형을 만들어야 하는데, 반드시같은 숫자가 쓰여있는 변끼리만 닿아 있어야 한다. 삼각형을 뒤집을 순 없다. 완성된 육각형은 다음과 같다. 점수를 계산하는 기준은 육각형의 각 변에 쓰인 숫자들의 합이다. 당신은 어떤 삼각형 세트를 부여받았을때 그 세트에서 나올 수 있는 최고점수를 계산하는 것이다. 입력 입력은 여러개의 세트로 이루어져 있다. 각 세트는 1이상 100이하의 정수 세개로 이루어진 수열 6개로 이루어져 있다. 수열 안의 수는 삼각형 변에 쓰여 있는 수를 시계방향으로 왼쪽부터 입력한 것이다. 세트는 별표(*) 하나를 포함하고 있는 줄로 구분된다. 마지막 세..

학부 연구생 민상 문제 학부 연구생으로 새로 연구실에 들어온 민상이는 사용할 자리를 정하려고 한다. 연구실은 격자 모양으로 되어있고 에어컨에서 바람이 상,하,좌,우 $4$방향으로 분다. 물론 에어컨이 위치한 곳에도 바람이 분다. 민상이는 더위를 많이 타서 에어컨 바람이 지나가는 곳 중 하나를 선택하여 앉으려고 한다. 연구실에는 다양한 물건들이 있어 바람의 방향을 바꾼다. 연구실에 있는 물건의 종류는 총 4가지가 있다. 아래 화살표의 의미는 바람이 각 물건에서 바람의 이동을 표시한 것이다. 물건 종류 물건 모양 바람의 이동 방향 물건 1 물건 2 물건 3 물건 4 연구실 어디든 민상이가 앉을 수 있는 자리이다. 즉 에어컨이 위치한 자리와 물건이 있는 자리 모두 앉을 수 있다. 민상이가 원하는 자리는 몇 개..

전기 요금 문제 최근에 전기 회사는 전기 요금을 또 올렸다. 새로운 전기 요금은 아래 표에 나와있다. (사용량은 항상 양의 정수) 사용량 (Watt-hour) 요금 (원) 1 ~ 100 2 101 ~ 10000 3 10001 ~ 1000000 5 > 1000000 7 위의 표를 읽는 방법은 다음과 같다. 사용량의 첫 100Wh의 가격은 1Wh당 2원이다. 다음 9900Wh (101 ~ 10000)의 가격은 1Wh당 3원이다. 이런식으로 계속 계산한다. 예를 들어, 10123Wh를 사용했을 때, 내야하는 요금은 2×100 + 3×9900 + 5×123 = 30515원이다. 전기 회사는 전기 요금을 인상하지 않고 돈을 더 버는 이상한 방법을 만들었다. 그 방법은 바로 사용한 전기의 양을 알려주지 않고, 얼마..

1루수가 누구야 문제 어느 무더운 여름날, 선린 야구부 앞으로 의문의 음료수가 도착했다! "이거 마시고 힘내! - 1루수에게 😍" 선수들은 서로 자기가 1루수라며 누가 1루수다 아니다로 싸우기 시작했다. 총 9명이 싸우고 있는데, 9명 중 한 명이 거짓말을 하고 있는 것 같다! 선수들은 아래 중 하나를 주장하고 있다. (편의상 선수들은 1, 2, ..., 9의 등번호로 구분하자.) 1 A: 선수 A가 1루수이다. 0 A: 선수 A는 1루수가 아니다. 선수들의 설전을 지켜보던 감독님이 답답해서 한마디 했다. "1루수가 누구야 2루수 이름이 뭐야 3루수는 몰라" 당신은 이제 '정확히 한 명이 거짓말을 하고 있다'는 가정과 '1루수는 정확히 한 명 존재한다'는 사실을 바탕으로 논리적 추론을 통해 특정 인물이 ..