2019.03.09) 백준 주제가 섞여버렸.. - 1300, 2805 (PyPy3)

2019. 3. 9. 13:50프로그래밍(주력)/백준 문제풀이

이번엔 문제가 좀 재밌었다.

풀이대로 푸니까 풀려서 좀 성취감이 든다고 해야하나.

그리고 이진탐색은 초기값을 잘설정해줘야 한다. 제로디비전이 많이 뜨는 주제중 하나.


1654번

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
c, n = map(int, input().split(' '))
= [int(input()) for i in range(c)]
l.sort()
 
# 1 이하로 자르면 큰일남 100% 런타임에러가 이 이유
left = 1
right = l[-1]
re = 0
# 이분탐색 시작
while left <= right:
    mid = (left + right) // 2
    su = 0
    # 현재 mid값으로 나눈 값 합
    for i in l:
        su += i // mid
 
    # 만약 자른 수가 원하는 수보다 많으면
    if n <= su:
        # 출력용 값 저장
        re = mid
        left = mid + 1
    else:
        right = mid - 1
 
print(re)
 
cs

2583번

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
h, w, c = map(int, input().split(' '))
= [[0 for j in range(w)]for i in range(h)]
visited = [[False for j in range(w)]for i in range(h)]
 
# 2차원 배열 생성 솔직히 위아래 뒤집혀도 상관없음
for i in range(c):
    w1, h1, w2, h2 = map(int, input().split(' '))
    for j in range(h1, h2):
        for k in range(w1, w2):
            l[j][k] = 1
 
re = list()
 
for j in range(h):
    for i in range(w):
        if not visited[j][i]:
            # 0을 기준으로 탐색
            if l[j][i] == 0:
                count = 0
                stack = [(j, i)]
                while stack:
 
                    j, i = stack.pop()
                    if not visited[j][i]:
                        visited[j][i] = True
                        count += 1
                        if j > 0 and not visited[j - 1][i] and l[j - 1][i] == 0:
                            stack.append((j - 1, i))
                        if i > 0 and not visited[j][i - 1and l[j][i - 1== 0:
                            stack.append((j, i - 1))
                        if j < h - 1 and not visited[j + 1][i] and l[j + 1][i] == 0:
                            stack.append((j + 1, i))
                        if i < w - 1 and not visited[j][i + 1and l[j][i + 1== 0:
                            stack.append((j, i + 1))
 
                re.append(count)
            visited[j][i] = True
 
re.sort()
print(len(re))
for i in re:
    print(i, end=' ')
 
cs