반응형

9655

https://www.acmicpc.net/problem/9655

 

9655번: 돌 게임

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
11
12
import sys
N = int(sys.stdin.readline())
dp = [-1]*1001
dp[1] = 1
dp[2] = 0
dp[3] = 1
for i in range(4, N+1):
    if dp[i-1] or dp[i-3]:
        dp[i] = 0
    else:
        dp[i] = 1
print('CY' if dp[N] == 0 else 'SK')
 cs

.

.

.

[풀이]

dynamic programming를 이용할 수 있는 문제.

규칙을 발견할 때까지 몇번 해보면 알 수 있다.

돌이 3개 또는 1개가 남는 순간 승패가 결정된다.

따라서 dp에 값을 저장시켜가며 결과에 도달할 수 있다.

 

그런데 하다보면 간단한 사실을 깨달을 것이다.

N이 홀수일 때와 짝수일 때에 따라서 승패가 결정된다.

9656번도 같은 문제이므로 다음 문제를 보자.

 

9656

https://www.acmicpc.net/problem/9656

 

9656번: 돌 게임 2

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

www.acmicpc.net

[정답]

1
print('SK' if int(input())%2 == 0 else 'CY')
 cs

.

.

.

[풀이]

9655번이랑 같은 문제인데 승패만 뒤집혀 결과값이 반대로 나오는 문제이다.

똑같이 해주고 결과값만 반대로 출력해주면 된다.

앞서 홀짝에 따라 결과가 바로 나오는 것을 알아챘다.

따라서 간단하게 한줄로 코딩하여 풀 수 있다.

 

p.s.

처음에 어떻게 해야하는 문제인가 싶었지만 6회정도 손으로 적어보니 완벽히 파악되는 문제였다.

왜 같은 문제가 여러개 있는지도 의문이다.

문제가 의도한 것이 dp였겠지 싶어서 dp로 끄적여봤다.

베스킨라빈스 31이 생각나는 문제다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 1449] 파이썬 : 수리공 항승  (0) 2021.10.22
[백준 7785] 파이썬 : 회사에 있는 사람  (0) 2021.10.17
[백준 2947] 파이썬 : 나무 조각  (0) 2021.10.15
[백준 1026] 파이썬 : 보물  (0) 2021.10.14
[백준 10157] 파이썬 : 자리배정  (0) 2021.10.13
반응형

2947

https://www.acmicpc.net/problem/2947

 

2947번: 나무 조각

첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다.

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
import sys
a = list(map(int, sys.stdin.readline().split()))
for i in range(len(a)-1):
    for j in range(len(a)-1-i):
        if a[j] > a[j+1]:
            temp = a[j]
            a[j] = a[j+1]
            a[j+1] = temp
            print(' '.join(map(str, a)))
 cs

.

.

.

[풀이]

Bubble sort, 버블 정렬 문제다.

그냥 bubble sort의 개념을 묻고 있다.

 

n개의 수에서

처음부터 순서대로 두 값을 비교하여 큰 값이 오른쪽으로 가도록 한다.

n-1번 반복하여 한 사이클을 돌면 최댓값이 맨 오른쪽 끝(a[n-1])으로 가 있을 것이다.

 

다시 처음부터 값 비교를 해준다. 이 때 최댓값이 맨 오른쪽(a[n-1])에 있기 때문에

 a[n-2]까지만 비교를 해준다. 

 

즉, n-1, n-2, ..., 1번 반복하게 된다.

끝이다.

 

p.s.

정렬 종류에는 여러가지가 있다. 하나씩 완벽하게 이해하자.

버블 정렬은 그 중에서 제일 간단한 것이다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 7785] 파이썬 : 회사에 있는 사람  (0) 2021.10.17
[백준 9655, 9656] 파이썬 : 돌 게임  (0) 2021.10.16
[백준 1026] 파이썬 : 보물  (0) 2021.10.14
[백준 10157] 파이썬 : 자리배정  (0) 2021.10.13
[백준 2346] 파이썬 : 풍선 터뜨리기  (0) 2021.10.12
반응형

1026

https://www.acmicpc.net/problem/1026

 

1026번: 보물

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
import sys
N = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
total = 0
a = sorted(a)
c = sorted(b, reverse = True)
for n in range(N):
    total += a[n] * c[n]
print(total)
 cs

.

.

.

[풀이]

문제 조건을 지키지 않았다. 유감.

사실 문제 조건 자체가 애매하다.

"B에 있는 수를 재배열하면 안 된다"

B만 건드리지 않으면 된다는 것인가?

그러면 c라는 배열로 복사해서 재배열하는 것은 가능한거 아닌가?

 

B를 있는 그대로 사용하면서 푸는 것이 가능하겠지만,

조건을 비틀어 푸는 방법이 눈에 딱하니 보였다.

채점 프로그램이 이를 인지할 수 있는지도 의문이었고.

 

그러다 이 글을 봤다.

https://www.acmicpc.net/board/view/75907 

 

글 읽기 - 문제 풀이방법이 이해가지 않습니다..

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

답을 구할 때 더 효과적이고 간단한 방법이 있으면 이를 사용하라는 것이다.

실제 상황의 문제는 결국 도전자들이 쉬운 방법으로 답을 찾을 수 있는지 시험하는 것이라고.

 

어느 정도 동의할 수 있다.

물론 연습하는 입장에서 쉬운 길, 때론 꼼수인 방법을 쓰는 것은 적절치 못하다.

 

아무튼 이번엔 그냥 조건을 무시하고 풀었다. 역시 채점 프로그램은 조건을 무시했는지 알아차리지 못했다.

 

정석적인 방법을 찾아본 결과,

A만 오름차순으로 정렬한 뒤

A 배열 순서대로 최소값과

B에서max()로 최댓값을 찾아 곱한다.

B에서 그 값을 pop() 시키고 

 

n 번 반복하여 값들을 다 더한다.

 

p.s.

실력 향상엔 정로

실전 향상엔 ...

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 9655, 9656] 파이썬 : 돌 게임  (0) 2021.10.16
[백준 2947] 파이썬 : 나무 조각  (0) 2021.10.15
[백준 10157] 파이썬 : 자리배정  (0) 2021.10.13
[백준 2346] 파이썬 : 풍선 터뜨리기  (0) 2021.10.12
[백준 1758] 파이썬 : 알바생 강호  (0) 2021.10.12
반응형

10157

https://www.acmicpc.net/problem/10157

 

10157번: 자리배정

첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다.

www.acmicpc.net

[정답]

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
import sys
C, R = map(int, sys.stdin.readline().split())
a = [[0 for i in range(C+1)] for j in range(R+1)]
K = int(sys.stdin.readline())
if K > C*R:
    print(0)
else:
    for i in range(R+1):
        a[i][C] = -1
    for j in range(C+1):
        a[R][j] = -1
    cnt = 0
    n = 1
    i, j = 0, 0
    a[0][0] = 1
    while True:
        if n == K:
            break
        else:
            if cnt == 0:
                if a[i+1][j] == 0:
                    i += 1
                    n += 1
                    a[i][j] = n
                else:
                    cnt = 1
            elif cnt == 1:
                if a[i][j+1] == 0:
                    j += 1
                    n += 1
                    a[i][j] = n
                else:
                    cnt = 2
            elif cnt == 2:
                if a[i-1][j] == 0:
                    i -= 1
                    n += 1
                    a[i][j] = n
                else:
                    cnt = 3
            elif cnt == 3:
                if a[i][j-1] == 0:
                    j -= 1
                    n += 1
                    a[i][j] = n
                else:
                    cnt = 0
    print(j+1, i+1)
 cs

.

.

.

[풀이]

배열 입력 순서를 잘 생각해야하는 문제.

파이썬의 배열 순서와 문제의 배열 순서가 다르다.

파이썬 형태를 그대로 쓰기 위해서 시계 반대 방향으로 좌석을 지정해줄 것이다.

먼저 a[R][C]까지 0인 배열을 선언해준 뒤

R행과 C열을 -1로 설정해준다. 테두리를 둘러싸주는 느낌.

 

c == 0 일 때 아래로(i +1)

c == 1 일 때 오른쪽으로(j + 1)

c == 2 일 때 위로(i - 1)

c == 3 일 때 왼쪽으로(j - 1)

이동하며 1씩 증가하는 n값 지정.

다음 단계에서 테두리에 만나거나 이미 입력된 값에 도착하면 c를 한 단계 높여주며 순환한다.

 

n이 K와 같아지면 while 종료하고 

문제 배열 순서와 마추기 위해

j+1, i+1 출력.

 

p.s.

코드를 보면 차근차근 풀었다는 모습이 보일 것이다.

그만큼 순서대로 생각만 하면 풀 수 있는 문제다.

아직 실력이 부족해 배열 순서 구조를 떠올리는데 시간이 꽤 소요되었다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 2947] 파이썬 : 나무 조각  (0) 2021.10.15
[백준 1026] 파이썬 : 보물  (0) 2021.10.14
[백준 2346] 파이썬 : 풍선 터뜨리기  (0) 2021.10.12
[백준 1758] 파이썬 : 알바생 강호  (0) 2021.10.12
[백준 1735] 파이썬 : 분수 합  (0) 2021.10.11
반응형

2346

https://www.acmicpc.net/problem/2346

 

2346번: 풍선 터뜨리기

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from collections import deque
import sys
N = int(sys.stdin.readline())
a = deque(enumerate(map(int, sys.stdin.readline().split())))
result = []
while a:
    num, i = a.popleft()
    result.append(num+1)
    if i > 0:
        a.rotate(-(i-1))
    else:
        a.rotate(-i)
for j in result:
    print(j, end = ' ')
 cs

.

.

.

[풀이]

문제 풀이의 핵심은 rotate()이다.

deque에서 사용 가능한 메서드.

일일이 pop(), append()하는 것도 가능하나 효과적인 메서드를 이용해보자.

 

예시)

arr = deque([0, 1, 2, 3, 4])

arr.rotate(1)

print(arr)--------------------> deque([4, 0, 1, 2, 3])

 

arr = deque([0, 1, 2, 3, 4])

arr.rotae(-2)

print(arr)--------------------> deque([2, 3, 4, 0, 1])

 

enumerate()를 사용하면 입력한 값 앞에 인덱스 번호를 붙여서 tuple 형태로 바꿔준다.

꽤나 유용하다.

 

p.s.

처음부터 코딩하자는 마음으로 평소에는 파이썬에만 있는 만들어진 모듈을 사용하는 것을 꺼린다.

한정적인 상황에서만 쓸 수 있는 모듈, 함수를 외우는 것은 코딩 실력 향상에 방해가 될 것이라 생각하기 때문이다.

deque는 특정 문제에만 쓰이는 것이 아니라 다방면에서 실용적으로 쓰일 수 있어 이용했다.

앞으로도 쓸만한 상황에서 자주 쓸 것 같다. 매우 편리하다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 1026] 파이썬 : 보물  (0) 2021.10.14
[백준 10157] 파이썬 : 자리배정  (0) 2021.10.13
[백준 1758] 파이썬 : 알바생 강호  (0) 2021.10.12
[백준 1735] 파이썬 : 분수 합  (0) 2021.10.11
[백준 10815] 파이썬 : 숫자 카드  (0) 2021.10.10
반응형

1758

https://www.acmicpc.net/problem/1758

 

1758번: 알바생 강호

첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
11
import sys
N = int(sys.stdin.readline())
a = []
total = 0
for n in range(N):
    a.append(int(sys.stdin.readline()))
a.sort(reverse = True)
for i in range(len(a)):
    if a[i] - i > 0:
        total += a[i] - i
print(total)
 cs

.

.

.

[풀이]

특별하지도 않은 간단한 문제.

sort(reverse = True)하면 내림차순으로 정리된다.

팁을 큰 값 순으로 받을 때 합이 최대가 된다.

종이에 몇번 끄적여 보면 바로 이해될 것이다.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 10157] 파이썬 : 자리배정  (0) 2021.10.13
[백준 2346] 파이썬 : 풍선 터뜨리기  (0) 2021.10.12
[백준 1735] 파이썬 : 분수 합  (0) 2021.10.11
[백준 10815] 파이썬 : 숫자 카드  (0) 2021.10.10
[백준 18310] 파이썬 : 안테나  (0) 2021.10.09
반응형

1735

https://www.acmicpc.net/problem/1735

 

1735번: 분수 합

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

www.acmicpc.net

[정답]

1
2
3
4
5
6
7
8
9
10
11
12
import sys
a1, a2 = map(int, sys.stdin.readline().split())
b1, b2 = map(int, sys.stdin.readline().split())
def gcd(a, b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)
A = a1*b2 + b1*a2
B = a2*b2
C = gcd(A, B)
print(A//C, B//C)
 cs

.

.

.

[풀이]

유클리드 호제법으로 최대공약수를 구해 이용하는 문제이다.

수학에서 하는 것처럼 분모를 통분한 후 최대공약수로 약분하면 된다.

 

p.s.

통분할때 gcd 한번 쓰고 약분할때 gcd 한번 더 써서 처음 풀땐 코드가 길었다.

정답처럼 맨 끝에 한번만 하자.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 2346] 파이썬 : 풍선 터뜨리기  (0) 2021.10.12
[백준 1758] 파이썬 : 알바생 강호  (0) 2021.10.12
[백준 10815] 파이썬 : 숫자 카드  (0) 2021.10.10
[백준 18310] 파이썬 : 안테나  (0) 2021.10.09
[백준 15654] 파이썬 : N과 M (5)  (0) 2021.10.09
반응형

10815

https://www.acmicpc.net/problem/10815

 

10815번: 숫자 카드

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,

www.acmicpc.net

[정답1]

1
2
3
4
5
6
7
8
9
10
11
12
import sys
N = int(sys.stdin.readline())
a_list = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
b_list = list(map(int, sys.stdin.readline().split()))
a_list = set(a_list)
for b in b_list:
    if b in a_list:
        print('1', end = ' ')
    else:
        print('0', end = ' ')
print()
 cs

.

.

.

[정답2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import sys
N = int(sys.stdin.readline())
a_list = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
b_list = list(map(int, sys.stdin.readline().split()))
a_list.sort()
def bin(x, y, s, e):
    if s > e:
        return 0
    mid = (s+e)//2
    if x == y[mid]:
        return 1
    elif x < y[mid]:
        e = mid - 1
    elif x > y[mid]:
        s = mid + 1
    return bin(x, y, s, e)
 
for b in b_list:
    result = bin(b, a_list, 0, len(a_list)-1)
    print(result, end = ' ')
 cs

.

.

.

[풀이]

주어진 값이 리스트에 있는 값인지만 찾아주면 되는 간단한 문제라고 생각해서 처음에 틀렸다. 시간복잡도를 생각해야된다고 한다.

[정답1]처럼 list를 set로 변환시켜주기만 하면 시간초과가 해결된다. 엄청 간단하다.

근데 시간복잡도에 관한 이유는 아직 이해하지 못했다.

 

[정답2]는 binary search, 이분탐색을 이용한 코드다. while을 써도 되고 재귀로 해도 되는데 재귀로 연습해봤다.

 

p.s.

요즘 엄청 쉬운 문제를 헤매고 있다. 쉬운걸 쉽게 푸는게 좋긴 하겠지만 완벽히 이해하려다 보니 시간이 지체되나보다.

외우고 넘어가며 빠르게 많이 푸는 것이 좋은걸까

이해하며 꼼꼼히 천천히 풀어도 괜찮은걸까.

반응형

'백준 문제풀이' 카테고리의 다른 글

[백준 1758] 파이썬 : 알바생 강호  (0) 2021.10.12
[백준 1735] 파이썬 : 분수 합  (0) 2021.10.11
[백준 18310] 파이썬 : 안테나  (0) 2021.10.09
[백준 15654] 파이썬 : N과 M (5)  (0) 2021.10.09
[백준 5555] 파이썬 : 반지  (0) 2021.10.08

+ Recent posts

티스토리툴바