동학 개발 운동

문제 출처 : 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/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/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 문제 해석 : 주사위를 굴리면서 바닥에 숫자가 있으면 복사하고, 없다면 주사위의 숫자를 바닥에 복사한다. 이렇게 명령을 진행할 때 마다 주사위 윗면의 수를 출력하는 문제이다. 문제 풀이 : 문제의 조건을 주의하면서 작성한다. 이때 주사위를 굴리는 경우에 따라서 변화하는 방향을 유의하면서 변경해주면 풀이할 수 있다. 풀이 시간 (기록..

문제 출처 : www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 문제 해석 : 마을을 두개로 분할 하려고 한다. 이때 마을 내부에 있는 길의 Cost가 최소가 되도록 마을을 분할 해야한다. 문제 풀이 : 최소 신장트리를 이용해서 마을 전체를 순회하는 도로를 구성한 다음 가장 큰 비용을 가진 길 하나를 제거하면 각자 모든 원소를 포함하는 2개의 마을 도로가 생성된다. 풀이 코드 import sys input = sys.std..

문제 출처 : www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 문제 해석 : 나누기 3, 나누기 2, 빼기 1을 수행해서 1로 만드는데 가장 적은 횟수의 연산을 한 경우를 찾는 것이다. 문제 풀이 : Q를 이용하면 풀 수 있다. 풀이 코드 from collections import deque N = int(input()) Q = deque() Q.append([N]) answer = [] while Q: arr = Q.popleft() x = arr[0] if x == 1: answer = arr break if x % 3 == 0: Q.append([x//3] ..

문제 출처 :www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 해석 : 계산의 우선순위를 변경하여 가장 작은 값을 결과로 가지도록 하는 문제이다. 즉 최대한 큰 수로서 - 연산을 진행하도록 하는 것이다. 문제 풀이 : 입력되는 문자열을 파싱하는 것을 시작으로 "-"를 기준으로 나누어 최대값으로 생성하고 그 뒤에 "-" 연산을 진행하게 되면 가장 작게 만들 수 있다. 가능한 다른 풀이 : 모든 경우를 생각해볼 수 있지만 비효율적일 수 있다. (ex, ..

문제 출처 :www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 해석 : 치킨 거리는 가장 가까운 치킨 집까지의 거리를 의미합니다. 이 문제에서는 도시 전체의 치킨 거리를 최소가 되게 하면서 치킨 집을 일정 숫자만큼 폐업 시켜야합니다. 문제 풀이 : 구현 문제 입니다. 가능한 모든 경우를 고려하여 치킨 집을 정해진 갯수만큼 배치하고 거리를 계산하여 최솟값을 찾아야합니다. 풀이 코드 from itertools import combinat..

문제 출처 : www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 해석 : 뱀이 사과를 먹으면 몸의 길이가 늘어나며 경로를 따라 움직입니다. 자신의 몸이나 벽에 부딪히면 게임이 끝나며 이때 시간을 출력합니다. 문제 풀이 : 구현 문제로서 문제에서 제시하는 조건들을 모두 만족시키게 차근차근 풀이를 진행하면 풀 수 있습니다. 풀이 코드 N = int(input()) K = int(input()) board = [[0] * N for _ in range(N)] for ..