문제:

전자 제품에는 저항이 들어간다. 저항은 색 3개를 이용해서 그 저항이 몇 옴인지 나타낸다.
처음 색 2개는 저항의 값이고, 마지막 색은 곱해야 하는 값이다.
저항의 값은 다음 표를 이용해서 구한다.

 색

값 

곱 

black 

brown 

10 

red 

100 

orange 

1000 

yellow 

10000 

green 

100000 

blue 

1000000 

violet 

10000000 

grey 

100000000 

white                                                        9                                                              1000000000


예를 들어, 저항에 색이 yellow, violet, red였다면 저항의 값은 4,700이 된다.


입력:

첫째 줄에 첫 번째 색, 둘째 줄에 두 번째 색, 셋째 줄에 세 번째 색이 주어진다. 색은 모두 위의 표에 쓰여 있는 색만 주어진다.


출력:

입력으로 주어진 저항의 저항값을 계산하여 첫째 줄에 출력한다.

풀이 방법:

항상 세 개의 명령을 받기 때문에 하나의 명령어 함수를 만들고 마지막 명령어일때에만 따로 구분을 두어서 곱하도록 만든다.
따라서 register라는 전역변수를 만든 후에 첫 번째, 두 번째 명령어일 때 이 값에 더해준다.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
first=input()
second=input()
third=input()
register=''
def regis(first,last=True):
    global register
    if last==True:
        if first=="black":
            register+='0'
        elif first=="brown":
            register+='1'
        elif first=="red":
            register+='2'
        elif first=="orange":
            register+='3'
        elif first=="yellow":
            register+='4'
        elif first=="green":
            register+='5'
        elif first=="blue":
            register+='6'
        elif first=="violet":
            register+='7'
        elif first=="grey":
            register+='8'
        elif first=="white":
            register+='9'
    else:
        register=int(register)
        if first=="black":
            register*=1
        elif first=="brown":
            register*=10
        elif first=="red":
            register*=100
        elif first=="orange":
            register*=1000
        elif first=="yellow":
            register*=10000
        elif first=="green":
            register*=100000
        elif first=="blue":
            register*=1000000
        elif first=="violet":
            register*=10000000
        elif first=="grey":
            register*=100000000
        elif first=="white":
            register*=1000000000
        print(register)
regis(first)
regis(second)
regis(third,False)
cs


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

[Programmers]Lv 3.디스크 컨트롤러  (2) 2019.05.06
[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1977. 완전제곱수  (0) 2019.05.03
[BOJ]1037. 약수  (0) 2019.05.02
[BOJ]2156. 포도주 시식  (0) 2019.05.01

문제:

M과 N이 주어질 때 M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합을 구하고 그 중 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 완전제곱수는 64, 81, 100 이렇게 총 3개가 있으므로 그 합은 245가 되고 이 중 최솟값은 64가 된다.

입력:

첫째 줄에 M이, 둘째 줄에 N이 주어진다. M과 N은 10,000이하의 자연수이며 M은 N보다 같거나 작다.

출력:

M이상 N이하의 자연수 중 완전제곱수인 겻을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 완전제곱수가 없을 경우는 첫째 줄에 -1을 출력한다.

풀이 방법:

math의 sqrt를 사용해서 풀어야 하는 문제이다. 첫 숫자 M의 sqrt를 구한 후 floor함수를 써서 lower_bound 값을 구하고, N에 sqrt를 구한 후 ceil 함수를 써서 upper_bound를 구한다. 이 구간을 반복문을 돌리면서 합을 구한 뒤에 더해진 answer 값이 없다면 -1을 출력하고 더해진 값이 있다면 upper_bound의 제곱수 값을 출력다.

1
2
3
4
5
6
7
8
9
10
11
12
13
import math
lower=int(input())
upper=int(input())
lower_bound=int(math.ceil(math.sqrt(lower)))
upper_bound=int(math.floor(math.sqrt(upper)))
answer=0
for i in range(lower_bound,upper_bound+1):
    answer+=i*i
if answer!=0:
    print(answer)
    print(lower_bound*lower_bound)
else:
    print(-1)
cs


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

[BOJ]8979. 올림픽  (0) 2019.05.05
[BOJ]1076. 저항  (0) 2019.05.04
[BOJ]1037. 약수  (0) 2019.05.02
[BOJ]2156. 포도주 시식  (0) 2019.05.01
[BOJ]2193. 이친수  (0) 2019.04.30

문제:

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력:

첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.

풀이 방법:

진짜 약수는 1과 N을 포함하고 있지 않으므로 진짜 약수들을 정렬한 뒤에 가장 첫값과 가장 마지막 값을 곱한 값이 N이 될 것이다. 

1
2
3
a=int(input())
answer=sorted(list(map(int,input().split())))
print(answer[0]*answer[-1])
cs


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

[BOJ]1076. 저항  (0) 2019.05.04
[BOJ]1977. 완전제곱수  (0) 2019.05.03
[BOJ]2156. 포도주 시식  (0) 2019.05.01
[BOJ]2193. 이친수  (0) 2019.04.30
[BOJ]1003. 피보나치 함수  (0) 2019.04.26

문제:

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력:

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1<=n<=10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.


출력:

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.


풀이 방법:

 동적계획법을 사용해서 최댓값을 찾아내야 한다. 일단 크게 두 가지 경우로 나눌 수 있다. 3이상 n 이하의 수 i에 대해서 i를 선택하는 경우와 선택하지 않는 경우이다.


i) i번째 값을 선택하고자 할 때

i번째 값을 선택하고자 하면 다시 두 개의 경우로 나눌 수 있다.


0x00   ,    ?0x0


전자는 i번째와 i번째를 연속해서 고르는 경우, 후자는 그렇지 않은 경우이다. 전자의 경우에는 i번째와 i번째를 더하고 거기에 dp[i-3]번째 값을 더하고, 후자의 경우에는 i번째 값에 dp[i-2]를 더하는 경우이다. 


ii) i번째 값을 선택하지 않을 때

위 경우를 먼저 계산해준 후 dp[i-1] 과 dp[i] 중 최댓값을 선택하면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
answer=[0]
a=int(input())
for i in range(a):
    answer.append(int(input()))
dp=[0]*(a+1)
dp[1]=answer[1]
if a>1:
    dp[2]=dp[1]+answer[2]
for i in range(3,len(dp)):
    dp[i]=max(answer[i]+answer[i-1]+dp[i-3],answer[i]+dp[i-2])
    dp[i]=max(dp[i-1],dp[i])
print(dp[a])
cs



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

[BOJ]1977. 완전제곱수  (0) 2019.05.03
[BOJ]1037. 약수  (0) 2019.05.02
[BOJ]2193. 이친수  (0) 2019.04.30
[BOJ]1003. 피보나치 함수  (0) 2019.04.26
[BOJ]9461.파도반 수열  (0) 2019.04.25

문제:

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1<=N<=90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다.

출력:

첫째 줄에 N자리 이친수의 개수를 출력한다.

풀이 방법:

직접 1번과 2번 규칙을 만족하는 수를 찾기 위해서 N자리의 이친수를 생성하는 일을 하면 시간초과, 메모리초과가 발생하게 된다. 즉 매우 큰 수이며 많은 작업이 필요하다. 따라서 규칙이 있음을 알게 되었다.

N=1일 때에는 [ 1 ] 하나이다. N=2일 때, [10] 하나이다. N=3일 때, [100, 101] 두 개이다. N=4일 때, [1000, 1001, 1010] 세 개다. .....

이렇게 계속 반복해 나가다 보면 피보나치 함수를 이루는 것을 알 수 있다. 즉 초기 두 항이 1, 1인 피보나치 함수이다.

1
2
3
4
5
6
7
n=int(input())
a,b=1,1
count=1
while(count<n):
    a,b=b,a+b
    count+=1
print(a)
cs


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

[BOJ]1037. 약수  (0) 2019.05.02
[BOJ]2156. 포도주 시식  (0) 2019.05.01
[BOJ]1003. 피보나치 함수  (0) 2019.04.26
[BOJ]9461.파도반 수열  (0) 2019.04.25
[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24

문제:

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

fibonacci(3) 을 호출하면 다음과 같은 일이 일어난다.


fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) (첫 번째 호출)을 호출한다.

fibonacci(2) 는 fibonacci(1) (두 번째 호출)과 fibonacci(0) 을 호출한다.

두 번째 호출한 fibonacci(1) 은 1을 출력하고 1을 리턴한다.

fibonacci(0) 은 0을 출력하고, 0을 리턴한다.

fibonacci(2) 는 fibonacci(1) 과 fibonacci(0) 의 결과를 얻고, 1을 리턴한다.

첫 번째 호출한 fibonacci(1) 은 1을 출력하고, 1을 리턴한다.

fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) 의 결과를 얻고, 2를 리턴한다.


1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.


입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력:

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

풀이 방법:

fibonacci(N)=fibonacci(N-1)+fibonacci(N-2)이기 때문에 0이 출력되는 횟수와 1이 출력되는 횟수도 피보나치를 이룬다. 0이 출력되는 횟수는 zero_f,zero_s라 하고, 1이 출력되는 횟수 one_f,one_s라 하고 이를 fibonnaci 함수에 넣으면 fibonacci(N)에서 0과 1이 각각 몇 번 출력되는지 알 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def new_fibo(n):
    zero_f,zero_s=1,0
    one_f,one_s=0,1
    count=1
    while(count<=n):
        zero_f,zero_s=zero_s,zero_f+zero_s
        one_f,one_s=one_s,one_f+one_s
        count+=1
    print(zero_f,one_f)
 
 
for i in range(int(input())):
    n=int(input())
    new_fibo(n)
cs


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

[BOJ]2156. 포도주 시식  (0) 2019.05.01
[BOJ]2193. 이친수  (0) 2019.04.30
[BOJ]9461.파도반 수열  (0) 2019.04.25
[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24
[BOJ]11052. 카드 구매하기  (0) 2019.04.23

문제:

위 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1,1,1,2,2,3,4,5,7,9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.


입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1<=N<=100)

출력:

각 테스트 케이스마다 P(N)을 출력한다.

풀이 방법:

수열 문제이므로 규칙을 찾는 것이 가장 중요하다. 파도반 수열은 다음과 같은 규칙을 가지고 있다.

P(N)=P(N-2)+P(N-3)

따라서 이를 처음에는 피보나치와 같이 재귀적 방법으로 풀려고 했으나 시간초과가 발생하게 되었다. 그래서 미리 길이 N의 배열을 만들어 놓고 반복문으로 배열의 인덱스를 참조하며 P(N)을 구하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for i in range(int(input())):
    number=int(input())
    answer=[0]*(number+1)
    if number==1 or number==2 or number==3:
        print(1)
    elif number==4:
        print(2)
    else:
        answer[1]=1
        answer[2]=1
        answer[3]=1
        answer[4]=2
        for i in range(5,number+1):
            answer[i]=answer[i-3]+answer[i-2]
        print(answer[number])
cs


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

[BOJ]2193. 이친수  (0) 2019.04.30
[BOJ]1003. 피보나치 함수  (0) 2019.04.26
[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24
[BOJ]11052. 카드 구매하기  (0) 2019.04.23
[BOJ]10844. 쉬운 계단 수  (0) 2019.04.22

문제:

정수 4를 1,2,3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력:

각 테스트 케이스마다, n을 1,2,3의 합으로 나타내는 방법의 수를 출력한다.

풀이 방법:

임의의 수 N을 1,2,3의 합으로 나타내는 방법은 크게 세 가지가 있다. N-1에서 1을 더해서 N이 되는 것, N-2에서 2를 더해서 N이 되는 것, N-3에서 3을 더해서 N을 되는 경우로 해서 총 3가지이다. 따라서 이를 재귀를 이용해서 풀었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
def one_two_three(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    elif n==3:
        return 4
    else:
        return one_two_three(n-1)+one_two_three(n-2)+one_two_three(n-3)
 
for i in range(int(input())):
    n=int(input())
    print(one_two_three(n))
cs
 


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

[BOJ]1003. 피보나치 함수  (0) 2019.04.26
[BOJ]9461.파도반 수열  (0) 2019.04.25
[BOJ]11052. 카드 구매하기  (0) 2019.04.23
[BOJ]10844. 쉬운 계단 수  (0) 2019.04.22
[BOJ]1149. RGB거리  (0) 2019.04.21

문제:

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

전설카드
레드카드
오렌지카드
퍼플카드
블루카드
청록카드
그린카드
그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 

예를 들어, 카드팩이 총 4가지 종류가 있고, P1=1, P2=5, P3=6, P4=7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

마지막으로, P1=3, P2=5, P3=15, P4=16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력:

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다.(1<=N,<=1,000)
둘때 줄에는 Pi가 P1부터 Pn까지 순서대로 주어진다.(1<=Pi<=10,000)

출력:

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

풀이 방법:

동적계획법을 사용해서 문제를 풀었다. N개를 갖기 위해 지불해야 하는 금액을 구하기 위해서 N-1개까지 지불해야하는 금액을 모두 구했다. 이를 통해 N개를 갖기 위해 지불해야 하는 최댓값을 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
dps=[]
number=int(input())
num_list=list(map(int,input().split()))
for i in range(number+1):
    dps.append([])
    for j in range(number+1):
        if i==j:
            dps[i].append(num_list[i-1])
        else:
            dps[i].append(0)
for i in range(2,len(dps)):
    for j in range(1,i):
        dps[i][j]=num_list[j-1]+max(dps[i-j][:i-j+1])
print(max(dps[-1]))
cs


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

[BOJ]9461.파도반 수열  (0) 2019.04.25
[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24
[BOJ]10844. 쉬운 계단 수  (0) 2019.04.22
[BOJ]1149. RGB거리  (0) 2019.04.21
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20

문제:

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질
때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력:

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력:

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이 방법:

길이가 하나 길어질수록 그 전의 길이에 영향을 받는다. 임의의 숫자 n에 대해서 생겨지는 계단 수의 수는 이전의 n-1 과 n+1의 수의 합이다. 하지만 끝값 0이나 9와 같은 경우에는 계단수를 유지하기 위해 각각 1과 8만 와야 하므로 이 경우에 대해서만 더해주도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
dp=[]
for i in range(int(input())+1):
    dp.append([])
    for j in range(10):
        if i==1:
            dp[i].append(1)
        else:
            dp[i].append(0)
for i in range(2,len(dp)):
    for j in range(10):
        if j==0:
            dp[i][j]+=dp[i-1][j+1]%1000000000
        elif j==9:
            dp[i][j]+=dp[i-1][j-1]%1000000000
        else:
            dp[i][j]+=dp[i-1][j-1]+dp[i-1][j+1]%1000000000
print(sum(dp[-1][1:])%1000000000)
cs


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

[BOJ]9095. 1,2,3 더하기  (0) 2019.04.24
[BOJ]11052. 카드 구매하기  (0) 2019.04.23
[BOJ]1149. RGB거리  (0) 2019.04.21
[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]1912. 연속합  (0) 2019.04.19

+ Recent posts