문제 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 풀이 각 도시에서 시작하여 모든 도시를 방문하고 다시 처음 도시로 돌아오는 한붓그리기 문제다. 간선의 비용이 다르고 경로의 정보를 저장해야하기 때문에 DFS를 사용한다. 외판원 최소 순회 비용인 min_value는 10억으로 초기화 한다. start: 시작 노드, current: 현재 노드, value: 현재 노드까지 쓴 비용, visited: 경..

문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 n - 1 번 순회하는 반복문으로 푼다. 매 반복마다 리터당 가격의 최소 값을 전역 변수(min_cost)에 저장하고, min_cost와 이동거리(road[i])의 곱을 전역 변수(total)에 누적해나간다. 코드 import sys n = int(sys.stdin.readline().rstrip()) roads = list(map(int, sys.stdin.readlin..

문제 https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 풀이 A와 B의 최대 길이는 50이기 때문에, A와 B의 최소 차이인 answer는 50으로 설정한다. A와 B를 비교할 때 A의 시작 지점을 기준으로 탐색한다. 경우의 수는 (len(B) - len(A) + 1)이다. 문제의 예제를 예를 들면, (A: adaabcX, B: aababbc)와 (A: Xadaabc, B: aababbc)인 두 가지 경우의..

문제 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 풀이 입력으로 받은 지민의 번호와 임한수의 번호를 jimin과 hansu라는 변수에 저장한다. while 반복문으로 jimin과 hansu가 같아질 때 까지 반복문을 돌고, 한번 반복할 때마다 jimin과 hansu는 각각 jimin // 2, hansu // 2 만큼 작아지고 라운드 수(cnt)를 1만큼 더해준다. 코드 import sys n, jimin, hansu = map(int, sys.s..

문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이 특정값 탐색에 유리한 해시 테이블 자료구조를 사용합니다. 해시 테이블에서 특정값 탐색의 시간 복잡도는 O(1)입니다. 파이썬에선 딕셔너리 타입으로 이를 구현합니다. isalpha()는 해당 문자열이 한글이나 알파벳으로만 이루어져있는지 확인하는 함수입니다. isdecimal()는 해당 문자열이 숫자로만 이루어져있는지 확인하는 함수입니다. 코드 import sy..

문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 풀이 이분 탐색을 이용하여 풉니다. n개의 예산 요청액들을 moneys 리스트에 저장하고 이분 탐색의 탐색 범위는 0부터 max(moneys)까지 입니다. 이분 탐색 반복문을 돌면서 총 예산 합(result)이 최대 예산(m)을 넘지 않으면서 가장 큰 값이 될 때의 최대 상한액(limit)을 구합니다. 코드 import sys def binary_search(left, right): r..