몽상실현개발주의

[BOJ] 1963 / 소수 경로 / Python 파이썬 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 [BOJ] 1963 / 숨바꼭질 문제와 유사한 문제였다. BFS 로 완전탐색을 하면서 memoization 으로 중복 탐색하는 경우를 제거하여 풀이하였다. 소수 판단은 "에라토스테네스의 체" 로 미리 만들어 주었고, 새롭게 생성되는 비밀번호는 자리수별로 0~9까지 변경하여 만들어 주었다. from collections import deque #..

[BOJ] 10971 / 외판원 순회2 / Python 파이썬 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 가장 기본적인 형태의 Traveling Salesman problem(TSP) 문제 이다. visited 로 방문한 경로를 check 하며 DFS 탐색하여 해결하였다. # 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. # 가..

[BOJ] 10819 / 차이를 최대로 / Python 파이썬 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 순열을 이용하여, 모든 경우를 만들어 비교하였다. from itertools import permutations N = int(input()) nums = list(map(int, input().split())) res = 0 for per in permutations(range(N), N): tmp = 0 for i in range(1, N)..

[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 주어진 숫자를 1, 2, 3 으로 표현하는 경우의 수는 점화식으로 표현 가능하다. dp(1) = 1 dp(2) = 2 dp(3) = 4 dp(4) = dp(1) + dp(2) + dp(3) dp(N) = dp(N-3) + dp(N-2) + dp(N-1) N = int(input()) nums = [0, 1, 2, 4] for _ in range(4, 12): nums.append(sum(nums[-3:])) for _ in..

[BOJ] 1451 / 직사각형으로 나누기 / Python 파이썬 https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이 www.acmicpc.net 풀이 브루트포스 알고리즘 문제로, 나눌 수 있는 경우를 모두 계산하여 해결하였다. 직사각형으로 나눌 수 있는 경우는 총 6가지가 나왔다. import sys input = sys.stdin.readline N, M = map(int, input().split()) nums = [] for _ in range(N): n..

[BOJ] 1107 / 리모컨 / Python 파이썬 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 처음 시도를 숫자가 조합되는 경우를 고려하는 방법으로 접근하였지만 풀지 못하였다. 다음 방법으로는 가능한 전체 채널 번호를 모두 탐색하는 방법으로 해결하였다. 이동하려고 하는 채널의 숫자가 비교적 작기 때문에, 완전탐색으로 충분히 가능하다는 것을 생각하지 못하고 어려운 방법 먼저 구상한것 같다. N = int(input()..

[BOJ] 1476 / 날짜 계산 / Python 파이썬 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 풀이 각각의 수 E, S, M을 1부터 시작하는 15, 28, 19 진법으로 생각하여 풀이하였다. check = [1, 1, 1] cnt = 1 while True: if check == ESM: print(cnt) break check[0] = (check[0] + 1) % 16 if not check[0]: check[0] = 1 check[..

[BOJ] 1744 / 수 묶기 / Python 파이썬 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 양수, 1, 0, 음의 정수에 대해 구분하여 계산해 주는 문제이다. 수열의 두 수를 묶어 최대값을 만들기 위해 다음과 같은 로직을 세웠다. 수열이 양수인 경우: 큰 수 부터 2개씩 묶어 곱하기 양수에 1이 포함 된 경우: 곱했을 경우 보다 더했을 경우가 더 큰 수가 된다. 수열이 음수인 경우: 작은 수 부터 2개씩 묶어 곱하기 0: 음..