문제 출처 : www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 1 . 문제 접근 방식 - 그리디 알고리즘의 대표적인 방법이라고 할 수 있다. 그리디 알고리즘이란 경우의 수가 많은 경우 가장 최적의 답을 선택해서 진행하는 방식을 말한다. 먼저, 기름값을 가장 핵심으로 생각했다. 출발 시에는 어쩔수 없이 주유를 하고 출발해야하지만 분명 기름값이 더 싼 곳은 존재할 것이다. 이를 이용하여 기름값의 배열을 돌며 작아질 경우에는 기름값을 재할당하며 거리..
파이썬3에서 입력받는 방법은 두 가지가 있다. 첫 번째는 가장 흔히 쓰이는 input()을 이용하는 것이다. 간단하게 알아보자. # 정수를 입력받고 싶을 때 N = int(input()) # 두 개의 정수를 입력받고 싶을 때 a, b = int(input().split()) # map함수를 이용하여 정수형태로 입력 받아 list에 저장 A, B = list(map(int, input().split())) 위와 같은 방법처럼 하나의 정수를 입력받을 수도 있고 여러 개의 정수를 입력받는 방법이 있다. 하지만 이러한 방법만 있는 것이 아니라는 말을 듣고 그에 대해 알아보려 한다. 새롭게 알게 된 방법은 두 번째로 sys.stdin.readline()을 이용하는 방법이다. 이 방식을 이용하기 위해서는 코드 첫 ..
문제 출처 : www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1 . 문제 접근 방식 - 파이썬에서 combination을 활용할 수 있는 모듈을 받아 부분집합을 다 구한뒤 전체 원소를 돌며 합이 S와 같아지는 경우를 찾기 2 . 내가 푼 코드 from itertools import combinations # N과 S를 입력 받음 N, S = map(int, input().split()) # N개의 수를 입력받아 list의..
문제 출처 : www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1 . 문제 접근 방식 - 알고리즘에 대한 고민 1. n을 입력 받음 2. n의 자리수 = m 3. n - m * 9 = x 생성자를 구하는 과정에서 나올 수 있는 최소값 4. x부터 n까지의 수를 검사하며 합을 구했을 떄 n값과 같아지는 최소 값 출력 2 . 내가 푼 코드 n = str(input()) m = int(len(n)) x = int(n) - m * 9 n..
