728x90
반응형

문제:

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

주의 사항:

정확하게 만들 수 없다면 -1을 출력한다.

풀이 방법:

while문을 사용해서 무게가 3인 봉지를 하나씩 늘리면서 필요한 무게가 5인 봉지의 수를 구하고, 다시 한 번 무게가 5인 봉지를 하나씩 늘리면서, 필요한 무게가 3인 봉지의 개수를 찾는다. 정확히 N킬로그램이 되는 경우만 배열에 넣는다. while문이 끝나고 배열의 길이가 1보다 크다면 그 중 가장 작은 값을 반환하고, 그렇지 않으면 -1을 출력한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def sugar(n):
    x=1
    count=[]
    while n//(3*x) > 0:
        if (n-3*x)%5 == 0:
            y= (n-3*x)//5
            count.append(x+y)
        x+=1
    y=1
    while n//(5*y) > 0:
        if (n-5*y)%3 == 0:
            x= (n-5*y)//3
            count.append(x+y)
        y+=1    
    if len(count)==0:
        return -1
    else:
        return min(count)
n=int(input())
print(sugar(n))
cs


728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]1110. 더하기 사이클  (0) 2019.04.02
[BOJ]4344. 평균은 넘겠지  (0) 2019.04.01
[BOJ]11718.그대로 출력하기  (0) 2019.03.30
[Programmers]Lv 2. 라면공장  (0) 2019.03.29
[Programmers]Lv 2. 영어 끝말잇기  (0) 2019.03.28
728x90
반응형

문제:

입력받은 대로 출력하는 프로그램을 작성하시오.

 

입력:

입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다.

각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시작하지 않고, 공백으로 끝나지 않는다.

 

풀이 방법:

문제만 보면 받은 그대로 print를 하면 될 것 같지만 정답 비율이 25% 정도인 것을 보면 풀기 쉽지 않다는 것을 알 수 있다. 대다수의 사람들이 통과를 하지 못하는 점은 주어지는 예제가 언제 끝나는지 모른다는 점이다. 따라서 이 점을 예외처리를 사용해서 해결한다면 문제를 통과 할 수 있다.

 

while True:
    try:
        line=input()
        print(line)
    except:
        break

 

 

728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]4344. 평균은 넘겠지  (0) 2019.04.01
[BOJ]2839.설탕 배달  (1) 2019.03.31
[Programmers]Lv 2. 라면공장  (0) 2019.03.29
[Programmers]Lv 2. 영어 끝말잇기  (0) 2019.03.28
[Programmers]Lv 2. 점프와 순간이동  (0) 2019.03.27
728x90
반응형

문제:

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

풀이 방법:

stock의 합이 k를 넘어가면 더이상 공급을 받지 않아도 된다. 그러므로 while의 조건을 stock<k 으로 잡았다. 기본적으론 남아있는 stock에 따라서 공급을 받을 수 있는 양이 다르게 된다. 예시에서와 같이 초기 stock이 4이므로 dates의 4일째인 20을 받을 수밖에 없다. 만약 기간 내에 여러 개의 날에서 공급을 받을 수 있다면 가장 많은 양을 받아오는 것이 적게 공급을 받도록 할 수 있다. 따라서 이 과정에서 우선순위 큐, 즉 힙을 사용하게 된다. stock에 따라서 받을 수 있는 공급들을 리스트에 담고 인덱스를 저장한다. 그리고 이 리스트 중에서 가장 많은 공급의 양을 빼서 stock에 더한다.
python에서 heapq라는 모듈을 제공해서 힙구조를 만들 수 있도록 한다. 하지만 이 힙은 최소힙을 제공하므로 힙구조에서 pop을 했을 때 최솟값이 나오게 된다. 하지만 이 문제에서는 최댓값을 빼야 하므로 최대 힙을 만들도록 한다. 따라서 힙에 넣을 당시에 heapq.heappush(h,(-supplies[i],supplies[i])) 와 같이 넣어서 최대힙을 구성하도록 하고 stock+=heapq.heappop(h)[1] 로 값을 빼도록 한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import heapq
def solution(stock, dates, supplies, k):
    answer = 0
    idx=0
    h=[]
    while(stock<k):
        for i in range(idx,len(dates)):
            if dates[i]<=stock:
                heapq.heappush(h,(-supplies[i],supplies[i]))
                idx=i+1
            else:
                break
        stock+=heapq.heappop(h)[1]
        answer+=1
    return answer
cs


728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]2839.설탕 배달  (1) 2019.03.31
[BOJ]11718.그대로 출력하기  (0) 2019.03.30
[Programmers]Lv 2. 영어 끝말잇기  (0) 2019.03.28
[Programmers]Lv 2. 점프와 순간이동  (0) 2019.03.27
[Programmers]Lv 2.소수 만들기  (0) 2019.03.26
728x90
반응형

문제:

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다..
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank ->kick ->know->wheel ->land->dream->mother->robot->tank

위 끝말잇기는 다음과 같이 진행됩니다.

* 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
* 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
* 3번 사람이 자신의 첫 번째 차례에 know을 말합니다.
* 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
* (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

끝말잇기에서 탈락하는 조건은 이전에 말했던 단어를 말하는 것과 잘못된 단어를 말하는 것이다. 이전에 말했던 단어임을 체크하기 위해서 past라는 배열을 만들어서 말한 단어들을 담았다. 다음 사람이 말한 단어가 past에 있으면 problem을 True로 바꿔주고 반복문을 종료하고 없다면 past에 넣고 마지막 두개의 값을 비교해 옳게 이어서 말했는지 확인한다. 이후 몇번째에 틀린것인지 확인하기 위해 divmod로 확인한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def solution(n, words):
    answer = [0,0]
    past=[]
    past.append(words[0])
    words.remove(words[0])
    count=0
    problem=False
    for word in words:
        count+=1
        if word in past:
            problem=True
            break
        else:
            past.append(word)
            if past[-2][-1]==past[-1][0]:
                pass
            else:
                problem=True
                break
 
    if not problem:
        return answer
    else:
        answer[1],answer[0]=divmod(count,n)
        answer[0]+=1
        answer[1]+=1
        return answer
cs


728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ]11718.그대로 출력하기  (0) 2019.03.30
[Programmers]Lv 2. 라면공장  (0) 2019.03.29
[Programmers]Lv 2. 점프와 순간이동  (0) 2019.03.27
[Programmers]Lv 2.소수 만들기  (0) 2019.03.26
[Programmers]Lv 3.단어 변환  (0) 2019.03.25
728x90
반응형

문제:

00 연구소는 한 번에 K 칸을 앞으로 점프하거나,(현재까지 온 거리) x 2에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간 이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러가지입니다.

* 처음 위치 0에서 5칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5만큼 듭니다.
* 처음 위치 0에서 2칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리: 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3만큼 듭니다.
* 처음 위치 0에서 1칸을 앞으로 점프한 다음 순간이동 하면(현재까지 온 거리: 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리: 2) x 2만큼 이동할 수 있으므로 위치 4로 이동합니다. 이 때 1칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

풀이 방법:

건전지 사용량을 적게 사용하려면 순간 이동을 많이 사용할 수록 좋다. 따라서 거리가 1, 2 ,4 ,8 ,16,.......과 같은 경우 건전지 사용량이 1이 되게 된다. 처음에만 점프를 하고 그 뒤부턴 계속 순간 이동을 하면 되기 때문이다. 이 점에서 규칙을 찾을 수 있었다. 거리를 2진수의 숫자로 바꿨을 때 1의 갯수가 필요한 점프의 갯수이다. 점프의 갯수가 건전지의 사용량이 되기 때문에 답이 된다.

1
2
3
4
5
6
def solution(n):
    ans=0
    while (n!=0):
        n,b=divmod(n,2)
        ans+=b
    return ans
cs


728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[Programmers]Lv 2. 라면공장  (0) 2019.03.29
[Programmers]Lv 2. 영어 끝말잇기  (0) 2019.03.28
[Programmers]Lv 2.소수 만들기  (0) 2019.03.26
[Programmers]Lv 3.단어 변환  (0) 2019.03.25
[Programmers]Lv 2. N개의 최소공배수  (0) 2019.03.24
728x90
반응형

문제:

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

nums를 3개의 for를 사용해서 nums 중 3개를 골라 더한 경우의 수를 구할 수 있다. 그리고 이 경우의 수들을 is_prime에 라는 함수에 넣어 소수인지 하나씩 판별을 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def is_prime(x):
    if x > 1:
        for i in range(2, x):
            if x % i == 0:
                return False
    else:
        return False
    return True
 
def solution(nums):
    answer_list=[]
    for i in range(len(nums)-2):
        for j in range(i+1,len(nums)-1):
            for k in range(j+1,len(nums)):
                answer_list.append(nums[i]+nums[j]+nums[k])
    count=0
    for i in answer_list:
        if is_prime(i):
            count+=1 
        else:
            pass
    return count
cs


728x90
반응형
728x90
반응형

문제:

두 개의 단어 begin,target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"] 라면 "hit" -> "hot" -> "dot" ->"dog" ->"cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin,target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

깊이/너비 우선 탐색(DFS/BFS) 중 너비 우선 탐색을 사용하는 문제이다. begin에서 변환 할 수 있는 경우의 수를 만들어 주고 이 중에서 target이 있는지 확인한다. 없다면 이 경우의 수를 누적하여 다음 단계를 진행한다. 즉 1단계에서 만들어질수 있는 모든 경우, 2단계에서 만들어지는 경우..가 되는 것이다. 어짜피 target이 있는 층만 알면 되기에 문제 없다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def solution(begin,target,words):
    answer=[begin]
    if target not in words:
        return 0
    answer_count=0
    while(len(words)!=0):
        for i in answer:
            temp=[]
            for word in words:
                count=0
                for j in range(len(i)):
                    if i[j]!=word[j]:
                        count+=1
                    if count==2:
                        break
                if count==1:
                    temp.append(word)
                    words.remove(word)
        answer_count+=1
        if target in temp:
            return answer_count
        else:
            answer=temp
    return 0
cs


728x90
반응형
728x90
반응형

문제:

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

풀이 방법:

일단 최소공배수를 구하기 위해서 최대공약수(gcd)를 구하는 함수도 필요하다. 왜냐하면 최소공배수는 두 수의 곱을 최대공약수로 나눈 값과 같기 때문이다. N개의 최소공배수를 구하는 것도 크게 다르지 않다. N개가 있다면 그 중 계속 2개를 골라서 최소공배수를 구하고 그 값을 다시 arr 배열에 담는다. 이 과정을 arr의 원소가 1개가 남을 때까지 하면 그 남은 원소가 N개의 수들의 최소공배수가 되는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def gcd(a,b):
    a,b=max(a,b),min(a,b)
    while b > 0:
        a,b=b,a%b
    return a
def solution(arr):
    while len(arr) !=1:
        a=arr.pop()
        b=arr.pop()
        c=gcd(a,b)
        arr.insert(0,int(a*b/c))
    answer=arr[0]
    return answer
cs


728x90
반응형
728x90
반응형

문제:

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
각 사원은 딱 한 번씩 경기를 합니다.
각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그 다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때,B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

풀이 방법:

B팀이 최대한 많이 이기려면 A팀의 숫자와 많이 차이 나지 않게 이기는 것이 중요하다. 즉 예를 들어서 A팀의 숫자가 4이고 B팀의 숫자 중에 5와 9가 남아 있다면 둘 중 어느 것을 내도 이기지만 5를 내서 이겨 9를 아끼는 방법을 사용하는 것이다. A,B를 내림차순으로 정렬을 하고, 각 A의 원소당 최소 차이가 나는 B를 선택한다. 만약 A의 값이 더 크다면 그냥 넘어가지만 A를 이기는 B가 있다면 그 값을 제거하고 answer을 1 증가시킨다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(A, B):
    answer = 0
    A=sorted(A,reverse=True)
    B=sorted(B,reverse=True)
    for i in A:
        v_min=i
        for j in range(len(B)):
            if B[j]>v_min:
                v_min=B[j]
            else:
                break
        if v_min==i:
            pass
        else:
            B.remove(v_min)
            answer+=1
    return answer
cs


728x90
반응형
728x90
반응형

문제:

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

풀이 방법:

처음엔 title 함수를 사용하고자 했다. title은 문자열에서 각 단어의 첫단어를 대문자로 만드는 내장함수이다. 하지만 첫번째 입출력 예시와 같이 첫 문자가 숫자라면 그 다음 문자를 소문자로 유지해야 하지만 title은 대문자로 리턴을 해버린다.
그 이후로는 split 공백을 지우고 첫 단어만 대문자로 만든 뒤(숫자에도 upper 연산이 가능하다) 이를 배열에 담아 join으로 담으려고 했으나, 공백이 하나가 아닌 2개이상일 수도 있었다.
따라서 최종적으론 upper라는 bool 변수를 만들어서 공백을 만나면 True로 켜지고 upper연산을 하고 난 뒤에는 False로 꺼지게 하였다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def solution(s):
    s=s.lower()
    a=''
    upper=True
    for i in s:
        if upper:
            if i==" ":
                a+=i
                continue
            a+=i.upper()
            upper=False
        else:
            if i==" ":
                a+=i
                upper=True
            else:
                a+=i
    return a
cs


728x90
반응형

+ Recent posts