티스토리 뷰

A. Card Game Contest (백준 14551)
조합론
각각의 덱은 독립적이므로 총 방법의 수는
import sys | |
input = sys.stdin.readline | |
n, m = map(int, input().split()) | |
ans = 1 | |
for _ in range(n): | |
x = int(input()) | |
if x == 0: x = 1 | |
ans = (ans*x)%m | |
print(ans%m) |
B. 행사장 대여 (Small) (백준 14732)
구현
범위가 작으므로 좌표를 받을 때마다 그 부분의 영역들을 2차원 배열에 1로 채워주면 된다. 이후 넓이를 구할 때 1의 개수를 세어주면 된다.
import sys | |
input = sys.stdin.readline | |
n = int(input()) | |
ans = [[0 for _ in range(501)] for _ in range(501)] | |
for _ in range(n): | |
x1, y1, x2, y2 = map(int, input().split()) | |
for i in range(x1, x2): | |
for j in range(y1, y2): | |
ans[i][j] = 1 | |
cnt = 0 | |
for i in range(501): | |
for j in range(501): | |
cnt += ans[i][j] | |
print(cnt) |
C. 체크포인트 달리기 (백준 29891)
그리디, 정렬
일단 들어오는 모든 수가 양수 혹은 음수일 때를 생각해보면,
import sys | |
input = sys.stdin.readline | |
n, k = map(int, input().split()) | |
a1 = [] | |
a2 = [] | |
for _ in range(n): | |
x = int(input()) | |
if x > 0: a1.append(x) | |
else: a2.append(abs(x)) | |
a1.sort(); a2.sort() | |
ans = 0 | |
res = len(a1) | |
while res > 0: | |
ans += a1[res-1]*2 | |
res -= min(res, k) | |
res = len(a2) | |
while res > 0: | |
ans += a2[res-1]*2 | |
res -= min(res, k) | |
print(ans) |
D. Hot Air Ballooning (백준 13915)
셋, 정렬
들어오는 수를 각각의 원소로 나누어 저장하고, 중복 제거하고 정렬을 해줬다. 정렬을 해주지 않으면 134와 143은 다른 수가 되어버리므로 정렬을 해서 똑같은 수임을 명시하기 위해서다. 다른 방법도 있겠지만 이게 생각하기 편했다. 그리고 set에 저장한 후 set에 있는 원소들의 개수를 출력하면 된다.
import sys | |
input = sys.stdin.readline | |
while True: | |
try: | |
n = int(input()) | |
d = set() | |
for _ in range(n): | |
x = ''.join(sorted(set(list(input().rstrip())))) | |
d.add(x) | |
print(len(d)) | |
except: | |
break |
E. 안정적인 문자열 (백준 4889)
스택
먼저 {}는 안정적인 문자열이므로 스택을 이용해서 제거한다. 모두 제거한 후 스택에 남아있는 문자들을 어떻게 처리할지 생각하면 된다. 항상 길이가 짝수인 문자열이 들어오기 때문에 스택에서 제거했던 것들도 모두 짝수 개만큼 제거되었으니 스택에 남아있는 문자들의 개수도 짝수다. 스택에서 2개의 문자를 뺀 후 2가지 방법을 떠올리면 된다.
첫 번째는 두 개의 문자열이 서로 같은 경우다. '{', '{'로 되어 있는 경우는 뒤의 문자를 '}'로 바꾸면 안정적인 문자열이 되고, '}', '}'인 경우는 앞의 문자를 '{'로 바꾸면 된다. 즉 바꾸기 연산을 1번 하면 된다.
두 번째는 서로 다른 경우이다. '{', '}'인 경우는 이미 안정적인 문자열이므로 처음 스택 부분에서 제거 되었으니 스택에 저장되어 있지 않다. 다르게 말해서 '}', '{'인 경우 밖에 없는데 앞 문자를 '{'로 변경하고, 뒷 문자를 '}'로 변경해야 하니 바꾸기 연산을 2번 해야한다.
import sys | |
input = sys.stdin.readline | |
case = 1 | |
while True: | |
s = input().rstrip() | |
if '-' in s: break | |
stack = [] | |
for i in s: | |
if not stack: | |
stack.append(i) | |
else: | |
if stack[-1] == '{' and i == '}': | |
stack.pop() | |
else: | |
stack.append(i) | |
cnt = 0 | |
while stack: | |
a1, a2 = stack.pop(), stack.pop() | |
if a1 == a2: cnt += 1 | |
else: cnt += 2 | |
print("{}. {}".format(case, cnt)) | |
case += 1 |
F. 아름다운 수열 (백준 21605)
구성적
둘 다
n = int(input()) | |
ans = [1] | |
now = [-1, 1] | |
cnt = 2*n-1 | |
i = 0 | |
while cnt > 0: | |
tmp = min(cnt, 3) | |
for _ in range(tmp): ans.append(now[i]) | |
cnt -= tmp | |
i ^= 1 | |
if n%3 == 2: ans[-1] = 1 | |
print(*ans[::-1]) |
G. 벼락치기 (백준 29704)
냅색
dp 테이블을 dp[마감 일까지 남은 일 수] = 벌금의 합의 최대로 정의했다. 만약 dp[2] = 8000이면, 현재 마감일까지 2일 남았고, 벌금 8000원을 내지 않아도 된다는 의미이다. 이 경우는 그냥 냅색으로 문제
import sys | |
input = sys.stdin.readline | |
n, t = map(int, input().split()) | |
d, c = 0, 0 | |
dp = [0 for _ in range(t+1)] | |
for _ in range(n): | |
di, mi = map(int, input().split()) | |
d += di; c += mi | |
for i in range(t, 0, -1): | |
if i-di >= 0: | |
dp[i] = max(dp[i], dp[i-di]+mi) | |
if d <= t: print(0); exit() | |
print(c-max(dp)) |
H. 땅 자르기 (백준 2175)
다각형의 넓이, 브루트포스
먼저 좌표 4개를 받고, 중점을 구한다. 이후 기준점을 다각형의 꼭짓점을 할지, 중점을 할지를 케이스를 나눠서 생각한다.
3개의 점을 이용해서 삼각형의 넓이를 구하고 누적 합해서 반으로 나눠졌을 때 나눠진 다각형의 값을 각각 구할 수 있다. 하나는 전체 넓이에서 지금 구한 다각형의 넓이가 될 것이고, 하나는 구한 다각형의 넓이가 될 것이다. 가장 비슷하게 맞추어야 하니 차의 절댓값이 가장 작은 값이 정답이다.
import sys | |
input = sys.stdin.readline | |
def polygon_area(arr): #already clockwise sorting | |
x, y = [], [] | |
for i in range(len(arr)): | |
x.append(arr[i][0]) | |
y.append(arr[i][1]) | |
x.append(arr[0][0]) | |
y.append(arr[0][1]) | |
r1, r2 = 0, 0 | |
for i in range(len(arr)): | |
r1 += x[i]*y[i+1] | |
r2 += y[i]*x[i+1] | |
return abs(r1-r2)/2 | |
x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split()) | |
d = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)] | |
total = polygon_area(d) | |
d2 = [((d[i%4][0]+d[(i+1)%4][0])/2, (d[i%4][1]+d[(i+1)%4][1])/2) for i in range(4)] | |
d3 = [] | |
for i in range(4): | |
d3.append(d[i]) | |
d3.append(d2[i]) | |
intv, ans1, ans2 = int(1e9), -1, -1 | |
for i in range(8): | |
area = 0 | |
if i&1: | |
for j in range(i+1, i+5): | |
area += polygon_area([d3[i], d3[j%8], d3[(j+1)%8]]) | |
a1, a2 = min(area, total-area), max(area, total-area) | |
if a2-a1 < intv: | |
intv = a2-a1 | |
ans1, ans2 = a1, a2 | |
else: | |
for j in range(i+2, i+5): | |
area += polygon_area([d3[i], d3[j%8], d3[(j+1)%8]]) | |
a1, a2 = min(area, total-area), max(area, total-area) | |
if a2-a1 < intv: | |
intv = a2-a1 | |
ans1, ans2 = a1, a2 | |
print(ans1, ans2) |
'BOJ' 카테고리의 다른 글
[BOJ][Python] 백준 32454번 - Fibonacci Lucky Numbers (0) | 2024.10.25 |
---|---|
[BOJ][Python] 백준 32242번 - |
2024.09.19 |
[BOJ][Python] 백준 9011번 - 순서 (0) | 2022.08.05 |
[BOJ][Python] 백준 16973번 - 직사각형 탈출 (0) | 2022.08.05 |
[BOJ][Python] 백준 4658번 - 삼각형 게임 (0) | 2022.08.03 |
- Total
- Today
- Yesterday
- Implementation
- DP
- Python
- 너비 우선 탐색
- 백트래킹
- Sorting
- 파이썬
- TEXT
- 위상 정렬
- greedy
- Brute Force
- 구현
- BOJ
- Topological Sorting
- 다이나믹 프로그래밍
- 볼록 껍질
- math
- backtracking
- 그리디
- 시뮬레이션
- MST
- set
- BFS
- 집합과 맵
- Simulation
- convex hull
- 정렬
- 수학
- 최소 신장 트리
- 브루트포스
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |