몽상실현개발주의

[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: 음..

[BOJ] 11399 / ATM / Python 파이썬 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 기다려하는 시간이 어떻게 counting 되는지를 먼저 생각하였더니 쉽게 해결하였다. ATM 에 다섯 사람이 대기한다고 생각해 보자 1번 : A 시간 / 2번 : B 시간 / 3번 : C 시간 / 4번 : D 시간 / 5번 : E 시간 1번부터 5번까지의 사람 순서대로 대기하였을때 counting 되는 시간은 A A+B A+B+C A+B+C+D A+B+C+D+E 가 ..