1. 문제 링크 www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 2. 문제 개요 제일 처음에 거북이는 (0,0)에 있고 연필을 내리고 있다. 축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU명령의 최솟값을 구하는 프로그램을 작성하시오. 3. 문제 힌트 각 직사각형들이 교차하거나 한 점에서 만나면 1번만 내리고도 다 그릴 수 있다. -> 한 칸이 연결되어 있다면 다 그릴 수 있다. -> BFS 그럼 '각 점이 교차한다거나, 한 칸이 연결되어 있..
1. 문제 링크 www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 www.acmicpc.net 2. 문제 개요 A, B, C 3개의 돌이 있다. 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 크기가 같지 않은 두 그룹을 고른다. 그다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 했을 때, X는 X+X로, Y는 Y-X개로 만든다. A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오. 3. 문제 힌트 가장 간단..
1. 문제 링크 www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 2. 문제 개요 8x8인 체스판에서 탈출하는 게임을 만들었다. 벽이 있는데 벽은 욱제가 움직일 때마다 밑으로 한 칸씩 움직인다. 욱제가 벽에 깔리면 게임은 끝난다. 욱제는 가만히 있거나 상하좌우 대각선으로 모두 9가지로 움직일 수 있다. 욱제의 캐릭터가 가장 왼쪽 아래에서 가장 오른쪽 위까지 이동할 수 있는지 없는지 구해보자. 3. 문제 힌트 시간개념을 더해보는 건 어떨까? 0초일 때..
1. 문제 링크 www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 개요 0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다. 1≤ i < j ≤ M 인 i와 j를 고른다. 그다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오. 3. 문제 힌트 그리디로 접근하려고 했으나..... 안 될 것 같다. 문제 유형을 보니 BFS..
1. 문제 링크 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청 www.acmicpc.net 2. 문제 개요 로봇 청소기를 사용해 청소를 하려고 한다. 경로는 유저가 직접 정할 수 있다. 방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하자. 3. 문제 힌트 더러운 지역의 개수가 최대 10개밖에 되지 않기 때문에 순열(permutation)을 사용해서 구현 가능하다. DP로 푸는 것은 아마 외판원 순회 ..
1. 문제 링크 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 � www.acmicpc.net 2. 문제 개요 지민이는 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기를 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수밖에 없다. 당연히, ..