문제:

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.


1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 

2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 

3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.


예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 


1. ‘()’ 인 괄호열의 값은 2이다.

2. ‘[]’ 인 괄호열의 값은 3이다.

3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.

4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.

5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.


예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.


여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

입력:

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30이하이다.

출력:

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

풀이 방법:

문제에서 제공된 예시케이스를 보면 예시케이스는 다음과 같이 계산이 되어야 한다.  2×(2+3×3)+2×3 사람이 직접 괄호를 보고 계산을 하면 이렇게 하겠지만 컴퓨터에게 이렇게 연산을 하게끔 하는 것은 어렵다. 따라서 위 식을 다음과 같이 변경하도록 할 것이다. 2×2+2×3×3+2×3 와 같이 괄호를 분배법칙을 이용해 풀어내었다. 이 규칙대로 하기 위해서 ( 나 [ 를 만나면 temp에 2 나 3를 곱하고 stack에 담아두고, ) 나 ] 를 만날 경우에는 그 전의 값이 ( 나 [ 일 경우에만 answer에 더해줬다.. 그 이유는 이 경우에만 올바른 괄호열이기 때문이다. 물론 앞에서 미리 temp에서 곱하면서 움직였으므로 값은 올바르게 구해진다. 그리고 스택의 top 값이 ( 나 [ 이면 pop 해줬다. 계속 이과정을 반복하다가 중간에 스택이 비어버렸는데 빼야하는 경우가 온다거나 끝까지 다 진행했는데도 아직 stack에 남아있다면 올바르지 않은 괄호열이기때문에 0을 출력하고 그렇지 않으면 answer를 출력하도록 한다.

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
answer=0
stack=[]
temp=1
correct=True
string=input()
for i in range(len(string)):
    if string[i]=="(":
        temp*=2
        stack.append("(")
    elif string[i]=="[":
        temp*=3
        stack.append("[")
    elif string[i]==")":
        if string[i-1]=="(":
            answer+=temp
        if not len(stack):
            correct=False
            break
        if stack[-1]=="(":
            stack.pop()
        temp//=2
    else:
        if string[i-1]=="[":
            answer+=temp
        if not len(stack):
            correct=False
            break
        if stack[-1]=="[":
            stack.pop()
        temp//=3
if (len(stack) or not correct):
    print(0)
else:
    print(answer)
cs


저작자표시 비영리 동일조건

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

[BOJ]2163. 초콜릿 자르기  (0) 2019.04.20
[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15

문제:

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 '(' 와 ')' 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PsS,VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 "()"문자열은 기본 VPS 이라고 부른다. 만일 x가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 "(x)"도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 "(())()"와 "((()))"는 VPS이지만 "(()(","(())()))", 그리고 "(()"는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS인지 아닌지를 판단해서 그 결과를 YES 와 NO로 나타내어야 한다.

입력:

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 테이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 테이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다 하나의 괄호 문자열의 길이는 2 이상 50이하이다.

출력:

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 "YES", 아니면 "NO"를 한 줄에 하나씩 차례대로 출력해야 한다.

풀이 방법:

스택을 사용해서 "(" 를 만난다면 +1을 해주고 ")"을 만난다면 -1을 해주는 작업을 하도록 한다. 이렇게 괄호 문자열을 모두 탐색하고 난다면 VPS와 같은 경우에는 count가 0이 된다. 그렇지 않다면 0이 아닌 값이 나올 것이다. 하지만 ")("와 같은 경우 VPS가 아니지만 count의 값이 0이 되게 된다. 그래서 ")"를 먼저 만나서 count가 음수가 되는 경우 역시 올바르지 않은 경우이다. 이를 조절해주면 문제 없이 문제가 풀릴 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for i in range(int(input())):
    count=0
    for j in input():
        if count < 0:
            count=100
            break
        if j=="(":
            count+=1
        else:
            count-=1
    if count==0:
        print("YES")
    else:
        print("NO")
cs


저작자표시 비영리 동일조건

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

[BOJ]1912. 연속합  (0) 2019.04.19
[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14

문제:

스택(stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는(pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO,Last In First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력:

첫 줄에 n (1<=n<=100,000)이 주어진다. 둘때 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력:

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

풀이 방법:

문제를 풀기에 앞서서 문제를 이해를 하는 것조차 어려웠다. 1~n까지의 수가 있을 때 각 수를 스택 구조를 유지하는 배열에 넣었다가 빼면서 우리가 입력으로 넣은 수열을 만드는 것이 문제의 목표이다. 


 처음에는 while로 넣었다가 빼는 과정을 조절하려고 했으나 적절한 조건을 찾기 어려웠다. 그래서 예외처리 구문을 사용해서 빈 리스트에서 pop을 하려 할 때 오류가 발생해서 빠져나오도록 만들었다. 

 

 우선 입력으로 처음 넣은 값을 만들기 위해서 그 값까지 모든 값들을 계속 순차적으로 넣어야 한다. 그래서 맨 처음 i로 반복되는 for 반복문이 첫 원소를 만들기 위한 과정이다. 이후 j 반복문을 통해서 본격적으로 원하는 수열을 만들고자 한다. 일단 우선적으로 answer가 비어있다면 하나 추가를 하는 과정을 거친 뒤 stack인 answer 배열의 맨 윗 값이 원하는 값인지 비교를 하는 조건문을 만들었다. 만약 원하는 값이라면 -를 하고 그렇지 않다면 아직 answer에 들어가 있지 않은 것이라면 반복문 i처럼 계속넣어주면 되기 때문에 이번에는 while로 넣어주도록 한다. 그리고 다시 끝 값을 비교하고 빼도록 한다. 


하지만 j-for를 반복하면서 더하거나 빼는 작업을 한 번도 하지 않았다면 이 것은 문제가 생긴 경우 이므로 somethingtodo라는 부울 함수를 사용해 NO를 출력하도록 한다. (주로 빼야할 수가 이미 들어가 있을 경우 발생한다.)


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
n=int(input())
def sol(n):
    answer_list=[int(input()) for i in range(n)]
    answer=[]
    ans=[]
    k=0
    try:
        for i in range(1,answer_list[0]+1):
            k+=1
            answer.append(k)
            ans.append("+")
        for j in range(n):
            somethingtodo=False
            if len(answer)==0:
                k+=1
                answer.append(k)
                ans.append("+")
                somethingtodo=True
            if answer[-1]==answer_list[j]:
                answer.pop()
                ans.append('-')
                somethingtodo=True
            else:
                while answer_list[j]>answer[-1]:
                    k+=1
                    answer.append(k)
                    ans.append("+")
                    somethingtodo=True
                if answer[-1]==answer_list[j]:
                    answer.pop()
                    ans.append("-")
                    somethingtodo=True
            if somethingtodo:
                pass
            else:
                print("NO")
                return
        print(*ans,sep="\n")
    except:
        print("No")
sol(n)
cs


저작자표시 비영리 동일조건

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

[BOJ]2504. 괄호의 값  (0) 2019.04.18
[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13

문제:

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

-push X: 정수 X를 스택에 넣는 연산이다.
-pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
-size: 스택에 들어있는 정수의 개수를 출력한다.
-empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
-top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 주어지는 명령의 수 N(1<=N<=10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.
주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력:

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이 방법:

python의 배열은 push와 pop이 스택과 동일하게 작동하므로 명령어가 들어오는 대로 수행해주면 문제 없이 통과 할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
answer=[]
for i in range(int(input())):
    a=input().split()
    if a[0]=="push":
        answer.append(int(a[1]))
    elif a[0]=="top":
        if len(answer):
            print(answer[-1])
        else:
            print(-1)
    elif a[0]=="size":
        print(len(answer))
    elif a[0]=="empty":
        if len(answer):
            print(0)
        else:
            print(1)
    else:
        if len(answer):
            print(answer.pop())
        else:
            print(-1)
cs


저작자표시 비영리 동일조건

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

[BOJ]9012.괄호  (0) 2019.04.17
[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]1181. 단어정렬  (0) 2019.04.12

문제:

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.


입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하며, 한 줄로 이루어져 있다. (n<=123456)

출력:

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.


풀이방법:

이 문제도 에라토스테네스의 체의 원리를 사용해서 풀어야 하는 문제이다. 하지만 입력이 하나의 테스트 케이스가 아니라 여러 개의 테스트 케이스로 이루어져 있으므로 매번 에라토스테네스의 체를 이용해 배열을 만드는 것은 시간을 많이 소비하게 된다. 따라서 미리 한 번 최대케이스에 대해서 경우로 만들어 놓고 테스트케이스들에 대해서는 슬라이싱을 통해서 접근을 하도록 한다.

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
import math
def prime(n):
    is_prime=True
    if n==1:
        is_prime=False
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            is_prime=False
    return is_prime
h=list(range(1,123456*2+1))
h[0]=0
for i in range(len(h)):
    if h[i]==0:
        pass
    elif prime(h[i]):
        for j in range(i+h[i],len(h),h[i]):
            h[j]=0
while True:
    a=int(input())
    if a==0:
        break
    temp=sorted(list(set(h[a:2*a])))
    try:
        temp.remove(0)
    except:
        pass
    print(len(temp))
cs


저작자표시 비영리 동일조건

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

[BOJ]1874. 스택 수열  (0) 2019.04.16
[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]1181. 단어정렬  (0) 2019.04.12
[BOJ]6064. 카잉 달력  (0) 2019.04.11

문제:

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1<=M,N<=1,000,000)

출력:

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이 방법:

임의의 수 n이 소수인지 판별하기 위해서 n-1까지 다 나눠보는 것이 아니라 sqrt(n) 값까지 나눠서 나누어지지 않는다면 소수임을 알 수 있다는 것은 대부분 알고 있다. 하지만 1,000,000개의 수에 대해서 다 해보는 것은 아무리 sqrt(n) 값까지 나눠본다고 해도 많은 시간이 소요된다. 따라서 이렇게 큰 수가 소수인지 판별하기 위해서 사용되는 것이 에라토스테네스의 체이다.


 이 방법은 예를 들어 120이하의 소수들을 파악하기 위해서 120까지의 배열을 생성한 뒤에 우선 2가 소수인지 판별을 한다. 2는 소수인것이 자명하므로 2의 배수의 값을 0으로 바꾼다.(4,6,8,10,12,14,......) 다 바꾸고 난 뒤에 3도 소수이므로(쉽게 판별할 수 있다.) 3의 배수의 값들을 0으로 바꾼다.(6,9,12,15,.....)이후 원래 4의 값으로 이동을 했지만 이미 2의 배수의 경우일 때 0으로 바뀌어 있다. 0이면 어떤 소수의 배수임을 의미하므로 그냥 지나가게 설정을 한다. 이렇게 계속 0이 아닌 수를 만나면 소수인지 판별을 하고 0을 만나면 그냥 지나가도록 한다. 그러면 최종적으론 이 배열엔 소수와 0만 남아있는 배열이 된다.

그러면 set을 통해서 중복된 0의 값들을 다 제거하고 재정렬한뒤 0의 값을 빼준다면 소수만 남아있는 리스트가 된다. 따라서 이 문제도 에라토스테네스의 체 방법을 이용해서 풀면 시간초과가 발생하지 않고 풀 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import math
def prime(n):
    is_prime=True
    if n==1:
        is_prime=False
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            is_prime=False
    return is_prime
a,b=input().split()
a=int(a)
b=int(b)
h=list(range(1,b+1))
h[0]=0
for i in range(len(h)):
    if h[i]==0:
        pass
    elif prime(h[i]):
        for j in range(i+h[i],len(h),h[i]):
            h[j]=0
h=sorted(list(set(h[a-1:])))
h.remove(0)
for i in h:
    print(i)
cs


저작자표시 비영리 동일조건

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

[BOJ]10828. 스택  (0) 2019.04.15
[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1181. 단어정렬  (0) 2019.04.12
[BOJ]6064. 카잉 달력  (0) 2019.04.11
[BOJ]1475. 방번호  (0) 2019.04.10

문제:

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력:

첫째 줄에 단어의 개수 N이 주어진다. (1<=N<=20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력:

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

풀이 방법:

단어를 정렬하는 기준이 두가지 이다. 그래서 처음 리스트에 담을 때 단어와 단어의 길이를 함께 담아주도록 한다. 이후 단어를 정렬을 할 때 sorted의 key 파라미터를 이용하도록 한다. lambda l : (l[1],l[0]) 과 같이 key 값을 주었는데 이 말은 l[1]은 단어의 길이를 기준으로 우선 정렬을 하고, 만약 같다면 l[0] 단어를 기준으로 즉 사전 순으로 배열하도록 한다.


1
2
3
4
5
6
7
8
9
10
11
def dictionary(n):
    l=[]
    for i in range(n):
        s=input()
        l.append((s,len(s)))
    l=list(set(l))
    l=sorted(l,key=lambda l: (l[1],l[0]))
    for i in l:
        print(i[0])
n=int(input())
dictionary(n)
cs


저작자표시 비영리 동일조건

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

[BOJ]4948.베르트랑 공준  (0) 2019.04.14
[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]6064. 카잉 달력  (0) 2019.04.11
[BOJ]1475. 방번호  (0) 2019.04.10
[BOJ]2775. 부녀회장이 될테야  (0) 2019.04.09

문제:

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세우졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x,y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x<M이면 x'=x+1이고, 그렇지 않으면 x'=1이다. 같은 방식으로 만일 y<N이면 y'=y+1이고, 그렇지 않으면 y'=1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.


예를 들어, M=10 이고 N=12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.


네 개의 정수 M,N,x와 y가 주어질 때 <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

입력:

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M,N, x와 y가 주어진다. (1<=M,N <=40,000, 1<= x <= M, 1 <= y <= N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력:

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

풀이 방법:

최소공배수를 사용해서 푸는 방법도 있다고 하지만 규칙을 찾아서 풀어보려고 했다. 10 12의 케이스에 대해서 순서대로 해를 나열해보고 재배열 해보니 다음과 같이 표를 얻을 수 있었다.


1,1 

2,2 

3,3 

4,4 

5,5 

6,6 

7,7 

8,8 

9,9 

10,10 

1,11 

2,12 

3,1 

4,2 

5,3 

6,4 

7,5 

8,6 

9,7 

10,8 

1,9 

2,10 

3,11 

4,12 

5,1 

6,2 

7,3 

8,4 

9,5 

10,6 


지금은 x좌표를 고정으로 잡고 재배열을 한 경우이다. 테스트 케이스 중 3,9를 찾아야 하는 경우라면 3을 고정시키고 y좌표만 변경시키며 3,9가 존재하는지 찾아보면 된다. y좌표도 변하는 규칙을 찾을 수가 있는데 지금은 10,12인 경우이므로 한 줄이 넘어갈 때마다 (n-m)=-2씩 더해주면 된다. 그러면 3,9는 위 표에서 3,11 밑 행에 있음을 알 수 있다. 또한 이렇게 규칙적으로 y좌표가 변하기 때문에 while문을 사용해 y좌표를 바뀌어주다가 다시 원래의 수가 돌아온다면 존재하지 않는 케이스임을 알 수 있으므로 -1을 반환하면 된다.


다음은 위의 규칙에 따라 구하는 코드이다.


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
def maya(m,n,x,y):
    if m < n:
        count = y
        if count > m:
            x1=(y-1)%m+1
            x2=(y-1)%m+1            
            while x1 != x:
                x1=((x1+(n-m)-1)%m)+1
                if x1 == x2:
                    return -1
                count+=n
        else:
            x1=y
            x2=y
            while x1 !=x:
                x1=((x1+(n-m)-1)%m)+1
                if x1 == x2:
                    return -1
                count+=n
    else:
        count =x
        if count > n:
            y1=(x-1)%n+1
            y2=(x-1)%n+1
            while y1 !=y:
                y1=((y1+(m-n)-1)%n)+1
                if y1 == y2:
                    return -1
                count+=m
        else:
            y1=x
            y2=x
            while y1 !=y:
                y1=((y1+(m-n)-1)%n)+1
                if y1 == y2:
                    return -1
                count+=m
    return count
def repeat(n):
    for i in range(n):
        m,n,x,y=map(int,input().split())
        print(maya(m,n,x,y))
n=int(input())
repeat(n)
cs

  


저작자표시 비영리 동일조건

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

[BOJ]1929. 소수 구하기  (0) 2019.04.13
[BOJ]1181. 단어정렬  (0) 2019.04.12
[BOJ]1475. 방번호  (0) 2019.04.10
[BOJ]2775. 부녀회장이 될테야  (0) 2019.04.09
[BOJ]10250. ACM 호텔  (0) 2019.04.08

문제:

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

입력:

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력:

첫째 줄에 필요한 세트의 개수를 출력한다.

풀이 방법:

크게 두 가지 케이스만 생각해주면 된다. 6과 9를 제외하고 다른 숫자들중 자주 나타나는 숫자의 개수와 6과 9의 개수를 센 것을 반으로 나눈 것의 올림(6과 9는 서로 돌려서 사용할 수 있다.)을 구해 이 두 값 중 최댓값을 반환해주면 된다.

1
2
3
4
5
6
7
8
9
10
def plastic(n):
    a=[]
    import math
    for i in '01234578':
        a.append(n.count(i))
    min1= max(a)
    min2= math.ceil((n.count('6')+n.count('9'))/2)
    return max(min1,min2)
n=input()
print(plastic(n))
cs


저작자표시 비영리 동일조건

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

[BOJ]1181. 단어정렬  (0) 2019.04.12
[BOJ]6064. 카잉 달력  (0) 2019.04.11
[BOJ]2775. 부녀회장이 될테야  (0) 2019.04.09
[BOJ]10250. ACM 호텔  (0) 2019.04.08
[BOJ]2292. 벌집  (0) 2019.04.07

문제:

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, "a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다."는 계약 조항을 꼭 지키고 들어와야 한다. 

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력:

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1<=k<=14,1<=n<=14)

출력:

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

풀이 방법:

각각의 케이스가 주어질 때마다 값을 구하는 것 마다 밀 14x14 아파트를 만들어서 각 호수마다 들어가야 하는 사람들의 수를 미리 구하고 난 뒤 인덱스로 접근해서 출력하는 것이 제일 편하고 빠르게 풀 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
answer=[]
for i in range(15):
    answer.append([])
    for j in range(15):
        answer[i].append(0)
answer[0]=list(range(15))
for i in range(1,15):
    for j in range(15):
        answer[i][j]=sum(answer[i-1][:j+1])
n=int(input())
for i in range(n):
    a=int(input())
    b=int(input())
    print(answer[a][b])
cs


저작자표시 비영리 동일조건

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

[BOJ]6064. 카잉 달력  (0) 2019.04.11
[BOJ]1475. 방번호  (0) 2019.04.10
[BOJ]10250. ACM 호텔  (0) 2019.04.08
[BOJ]2292. 벌집  (0) 2019.04.07
[BOJ]2941. 크로아티아 알파벳  (0) 2019.04.06

+ Recent posts

티스토리툴바