BOJ 결혼식, 계단오르기

1. BOJ 5567 (결혼식)

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

5567번: 결혼식

코드

n = int(input())
m = int(input())
graph = [list(map(int, input().split())) for _ in range(m)]
f1 = []
f2 = []
for i in range(m):
    if graph[i][0] == 1:
        f1.append(graph[i][1])
 
for j in range(m):
    if graph[j][0] in f1:
        f2.append(graph[j][1])
    elif graph[j][1] in f1:
        f2.append(graph[j][0])
 
invited = set(f1 + f2)
if 1 in invited:
    invited.remove(1)
print(len(invited))

1. 입력이 다음과 같다. 6(인원 수), 5(리스트의 길이) 
graph에 친구 쌍을 더블array로 입력 받는다. 

6
5
2 3
3 4
4 5
5 6
2 5

2. f1은 상근(1)의 친구, f2는 친구의 친구이다. 

3. graph를 for문 돌면서 f1과 f2를 저장할 것인데, 문제에서 친구 쌍은 오름차순으로 입력된다고 나와있다. 
그러므로 graph[i][0]에 1이 있을 것이다. 우선 graph[i][0]==1일 때 친구 graph[i][1]를 f1 리스트에 저장한다. 

4. f1을 저장한 후에 다시 graph for문을 돌면서 f1의 친구들을 f2에 저장한다. 

5. f1과 f2의 중복을 제거하기 위해 set으로 변환한 후, 만약 이 set에 1(상근)이 포함되어 있다면, 제외한다. 
graph[j][1] in f1:
      f2.append(graph[j][0]) 에서 1이 추가될 수 있다.

 

 

2. BOJ 2579 (계단 오르기)

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

2579번: 계단 오르기

코드

n = int(input())
arr = []
for i in range(n):
    arr.append(int(input()))
result = [0 for _ in range(n)]
 
if n==1:
    result[0] = arr[0]
if n==2:
    result[1] = arr[0]+arr[1]
if n==3:
    result[2] = arr[2] + max(arr[1], arr[0])
 
if n>3:
    result[0] = arr[0]
    result[1] = arr[0] + arr[1]
    result[2] = arr[2] + max(arr[1], arr[0])
    for i in range(3, n):
        result[i] = arr[i] + max(result[i-2], arr[i-1]+result[i-3])
 
print(result[-1])

 

설명

1. 계단의 수가 (1,2,3, 3개 이상)일 때로 나눠서 구현하였다. 
2번 식에서 idx i-3을 사용하기 때문에 n=3일 때까진 예외처리를 해줘야한다. 

2. result[i] = arr[i] + max(result[i-2], arr[i-1]+result[i-3])

마지막 계단은 꼭 밟아야하기 때문에 우선 arr[i] 값에, 
1) 이전 계단(arr[i-1])을 더할 때, arr[i-2]은 밟으면 안된다. (연속 3칸은 밟을 수 없음)
그러므로, arr[i-1] + result[i-3] 
2) 2칸 전 계단 (arr[i-2])을 더할 때, result[i-2]를 더해주면 된다.