동학 개발 운동

문제 출처 : www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해석 : 홍수가 일어나고 있고, 고슴도치는 D를 향해서 물을 피해 가야합니다. 이때의 최소 시간을 구하는 문제입니다. 단 도달할 수 없을 경우 실패 문자를 출력합니다. 문제 풀이 : 간단한 BFS 알고리즘 통해서 풀 수 있습니다. 물의 이동과 고슴도치의 이동을 유심히 살펴 순서를 정의해주면서 탐색하면 됩니다. 풀이 시간 (기록용) : 30분 풀이 코드 import heapq dx = [0, 0, 1, -..

문제 출처 : www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 문제 해석 : 좋은 수열이란 수열 중 어느 수열도 인접한 수열이 같지 않다는 것이다. 문제 풀이 : 재귀함수를 이용해서 풀이할 수 있다. 풀이 시간 (기록용) : 30분 풀이 코드 import sys def check(s): for i in range(1, (len(s) // 2) + 1): leng = i start = 0 start2 = start + i for j in range(len(s) - (len..

문제 출처 : www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 해석 : 숫자가 들어있는 배열이 주어질 때 i에서 j 까지의 합을 구하는 문제이다. 문제 풀이 : 매 요청마다 직접 합을 구하면 시간초과가 나기때문에 처음부터 합을 구해놓고 요청마다 그 합을 출력해준다. 풀이 시간 (기록용) : 10분 풀이 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()..

문제 출처 : www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 문제 해석 : 주사위를 굴려서 1에서 100으로 이동하는데 걸리는 최소 주사위 굴리는 횟수를 구하는 문제이다. 문제 풀이 : heapq를 사용해서 BFS 형식으로 풀이할 수있다. 딕셔너리로 저장해 높은 사다리나 뱀인 경우에는 강제로 이동시키고, 그렇지 않을 경우 1~6칸을 이동시키면서 가장 먼저 100에 도달하는 경우에는 반복문을 빠져나온다. 풀이 시..

문제 출처 : www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 해석 : 자신의 왼쪽으로만 전파를 쏘는 타워가 있다. 이 전파를 수신하기 위해서는 이보다 큰 타워여야한다. 이때 자신의 전파를 받는 전파의 인덱스를 출력하라. 문제 풀이 : 일반적인 투포인터, 2중 for문으로는 500,000만개의 타워를 처리할 수 없기 때문에 Stack을 이용해야 한다. 풀이 시간 (기록용) : 1시간 풀이 코드 (Python) from collections import..

문제 출처 : www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 해석 : 맥주를 마시면서 걸어가면서 목적지 까지 도달할 수 있는지 결과를 출력하는 문제이다. 문제 풀이 : 플루이드 워셜 알고리즘을 사용하면 풀이할 수 있다. 풀이 시간 (기록용) : 45분 풀이 코드 #include #include #include #include #define INF 987654321 using namespace std; int main() { int T; cin >..

문제 출처 : www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 해석 : 구슬 게임을 진행한다. 상하좌우로 중력을 이용해서 구슬을 움직일 때 빨간 구슬만 탈출할 수 있는 경우에 걸리는 최소 시간을 출력하는 문제이다. 문제 풀이 : 문제의 요구 사항에 맞춰 문제 풀이를 진행하면 된다. 풀이 시간 (기록용) : 1시간 30분 풀이 코드 from collections import deque import copy..

문제 출처 : www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제 해석 : 체스말이 4개이상 모이거나 1000번을 해도 4개가 모이지 않으면 게임이 끝난다 이때 끝날 때 까지의 시간을 구하는 문제이다. (주어진 조건을 모두 충족하면서) 문제 풀이 : 문제에는 주어지는 조건이 있다. 체스판에 경우에 따라서 모든 경우를 차근차근 생각해서 풀이하면 된다. 풀이 시간 (기록용) : 1시간 32분 풀이 코드 dx = [0, 0, -1, 1] dy = [1, -1..

문제 출처 : www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제 해석 : 키의 대소 비교 결과가 M개 주어졌을 때 N 명의 학생들 가운데 자신의 키 순서를 정확하게 알고있는 사람의 수를 구하는 문제이다. 문제 풀이 : 그래프 탐색을 통해서 자신보다 작은 사람의 수, 자신보다 큰 사람의 수를 알고 있는 만큼 기록한다. 이후에 자신이 알고있는 사람의 키 순서가 N-1일때 그 사람은 자신의 키 순서를 정확하게 알고 있다고 볼 수 있다. 풀이 시간 (기록용) : ..

문제 출처 : www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 문제 해석 : 주사위를 굴리면서 바닥에 숫자가 있으면 복사하고, 없다면 주사위의 숫자를 바닥에 복사한다. 이렇게 명령을 진행할 때 마다 주사위 윗면의 수를 출력하는 문제이다. 문제 풀이 : 문제의 조건을 주의하면서 작성한다. 이때 주사위를 굴리는 경우에 따라서 변화하는 방향을 유의하면서 변경해주면 풀이할 수 있다. 풀이 시간 (기록..