log 2021-10-06

---

• sport
  • bj 2616
  • bj 1764 - 듣보잡

sport

bj 2616

아이디어 떠올리기 실패. dp 문제.

50000C3으로 해도 값이 너무 커서 시간초과고, 더 나은 방법이 생각나지 않았다. 부분 문제를 어떻게 정의해야 이런 dp 문제를 풀 수 있을까?

hint

해설 참조: https://comyoung.tistory.com/184

대수를 제한하고, 고려한 위치를 제한하면, 굉장히 쉬운 문제가 된다 (그냥 최대 부분합 문제). 이것을, 고려하는 위치를 늘려가면서, 그리고 대수를 늘려가면서 테이블을 채우면 답을 찾을 수 있다.

부분 구조: dp[i][j] = i번째 버스가 j번째 객차까지 고려했을 때 최대 운송 승객 수

그럼 이 부분 구조를 어떻게 구현하는가? dp[i][j]는 다음의 값 중 하나이다.

1. 이전 위치에서 소형 기관차를 추가하지 않은 경우: dp[i][j-1]이 답이 된다.
2. 이전 위치에서 소형 기관차를 추가한 경우: 소형 기관차의 객차수 m에 대해 dp[i-1][j-m]+(j-m 칸에 소형 기관차를 추가하여 얻는 값)이 답이 됨.

그런데, 그렇게 구현해도 틀렸는데, 정답 코드와 비교해 보니 j들을 계산할 때, 소형 기관차들이 겹칠 수 없도록 시작 위치를 조정해야 하는 것 같다.

부분합 인덱스 계산하는 부분이 헷갈림. 연습 필요.

bj 1764 - 듣보잡

쉬운 문제. 파이썬 set 집합 연산으로 풀이 가능

python solution

def solve():
    N,M = ria()
    aset = set()
    bset = set()
    for i in range(N):
        aset.add(rsa()[0])
    
    # print(aset)

    for i in range(M):
        try:
            bset.add(rsa()[0])
        except:
            pass

    # print(aset.intersection(bset))
    names = aset.intersection(bset)
    ans = sorted(list(names))
    print(len(ans))
    for i,v in enumerate(ans):
        print(v)
    pass
  

---