2023년 8월 11일 알고리즘 문제풀이
문제 1 백준 1010
1차 시도
나의 생각
결국 서쪽에 있는 사이트는 모두 사용 되야 하므로 첫번째 사이트부터 고를 수 있는 상황에 대해 dfs를 적용하고 모든 다리가 결정될 때마다 카운트하는 방법을 생각했다. 그런데 가만 생각해보니 다리끼리 교차될 수 없으므로 동쪽의 사이트 중 서쪽의 사이트의 갯수만큼 선택하면 다리가 연결되는 경우의 수는 한개 뿐이다. 따라서 조합(Combination)을 사용하면 되겠다고 판단했다. 모듈을 까먹어서 그냥 직접 구현했다.
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
t = int(sys.stdin.readline())
def combination(a, b):
tmp_u = tmp_d = 1
for i in range(a):
tmp_u *= (b-i)
for j in range(1, a+1):
tmp_d *= j
return tmp_u/tmp_d
for _ in range(t):
n, m = map(int, sys.stdin.readline().split())
ans = combination(n, m)
print(int(ans))
문제 2 백준 1308
1차 시도
나의 생각
우선 두 날짜의 ‘해’를 같은 날짜로 맞추고, 순서대로 달, 일 을 맞추는 방법을 생각했다. 그냥 빼기에는 꼭 끝나는 날짜의 달이나 일이 오늘 날짜의 달과 일보다 크다는 보장이 없었기 때문이다. 예를 들어 오늘이 2023년 8월 11일인데, 끝나는 날짜가 2024년 1월 2일 일 수도 있으니까.. 해를 맞추기 위해 365일을 더하고, 1월을 8월로 맞추려면 7번 뒤로 가야 하니 각각 30일 혹은 31일을 알맞게 빼주었다. 일수도 같은 방식을 취했다. 문제에서 주어진 예시 케이스는 알맞게 나왔는데, 정답에서 오답처리 되었다. 예외를 아직 찾지 못했다.
결과
오답
코드
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
import sys
y, m, d = map(int, sys.stdin.readline().split())
d_y, d_m, d_d = map(int, sys.stdin.readline().split())
def cal_year(a, b):
x = b - a
cnt_y_1 = x // 4
cnt_y_2 = x // 100
cnt_y_3 = x // 400
cnt_y = cnt_y_1 - cnt_y_2 + cnt_y_3
return 365*x + cnt_y
def month(x):
if x == 2:
return 28
elif x % 2:
return 31
elif x == 8:
return 31
elif not x % 2:
return 30
def cal_month(a, b):
cnt = 0
if a > b:
while a != b:
a -= 1
cnt -= month(a)
else:
while a != b:
a += 1
cnt += month(a)
return cnt
def cal_day(a, b):
return b-a
if d_y-y >= 1001:
print('gg')
elif d_y-y == 1000:
if d_m > m:
print('gg')
elif d_m == m:
if d_d >= d:
print('gg')
else:
ans = 1
ans += cal_year(y, d_y) + cal_month(m, d_m) + cal_day(d, d_d)
print('D-'+str(ans))
2차 시도
나의 생각
겨우 반례를 찾아냈다.. 정확히 1000년 차이가 날 때 오늘이 D-DAY의 달보다 클 때 아무것도 출력되지 않는다. 예를 들어, 오늘이 1000년 2월 1일이고, D-DAY가 2000년 1월 1일 이라면 기존 코드에서는 결과가 출력되지 않는다. 또 1000년 차이에 달이 같더라도 D-DAY의 일수가 작으면 마찬가지로 출력이 되지 않는다. 1000년 2월 10일과 2000년 2월 5일을 입력하였더니 결과가 나오지 않는다. if문을 너무 복잡하게 쓴 댓가를 치뤘나보다…
정답을 찾다가 본문을 고쳤다. 두 날 간의 격차를 계산하지 않고 1년 1월 1일부터 해당 날짜까지의 거리를 계산한 후 둘의 차이를 구하였다. D-DAY의 달이나 일수가 더 낮을 때 경우를 분류하는 것이 너무 복잡해서 한 선택이었다. 우선 입력값이 의미하는 바를 명확히 하기 위해 변수의 이름을 조금 길게 하였다. check_year은 paramter로 받은 해가 윤년이라면 True, 아니면 False를 반환한다. 1년부터 햇수가 증가하며 윤년일때는 366일, 아닐때는 355일 더했다. 또한 1월부터 해당 달까지 계산할 때 윤년일 경우는 2월은 29일로 처리하였다.
결과
정답
코드
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
import sys
start_year, start_month, start_day = map(int, sys.stdin.readline().split())
end_year, end_month, end_day = map(int, sys.stdin.readline().split())
def check_year(x):
if x%4:
return False
else:
if x%100:
return True
else:
if x%400:
return False
else:
return True
def calculate(a,b,c):
tmp = 0
for i in range(1,a):
if check_year(i):
tmp += 366
else:
tmp += 365
month = [0,31,28,31,30,31,30,31,31,30,31,30,31]
for i in range(1,b):
tmp += month[i]
if i == 2 and check_year(a) == True:
tmp += 1
tmp += (c-1)
return tmp
def answer(a,b,c,d,e,f):
ans = calculate(d,e,f) - calculate(a,b,c)
print(f"D-{ans}")
return
if end_year-start_year > 1000:
print("gg")
elif end_year-start_year == 1000:
if end_month>start_month:
print("gg")
elif end_month==start_month:
if end_day >= start_day:
print("gg")
else:
answer(start_year,start_month,start_day,end_year,end_month,end_day)
else:
answer(start_year,start_month,start_day,end_year,end_month,end_day)
else:
answer(start_year,start_month,start_day,end_year,end_month,end_day)
문제 3 백준 1316
1차 시도
나의 생각
글자를 하나씩 탐색하며 이전 글자를 저장하였다. 현재 글자와 비교하여 똑같으면 연속되고 있으므로 유지하고, 같지 않으면 새롭게 업데이트 하였다. 단, 기존의 가지고 있던 글자는 배열에 저장하였다. 새롭게 만난 글자가 배열에 존재한다면 연속되지 않는 문자가 나타났다는 의미이므로 순회를 종료했다. 순회가 종료되지 않으면 for-else문을 통해 그룹 단어로 개수를 셌다.
for-else문은 for 루프가 break 로 중간에 종료되지 않고 끝까지 순회를 완료하면 else 문이 실행되는 코드이다!
결과
정답
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
n = int(sys.stdin.readline())
cnt = 0
for _ in range(n):
word = sys.stdin.readline().rstrip()
arr = set()
k = len(word)
tmp = word[0]
for i in range(1,k):
if tmp != word[i]:
arr.add(tmp)
tmp = word[i]
if tmp in arr:
break
else:
cnt += 1
print(cnt)
