log 2020-02-14

---

할 일

알고리즘 문제풀이

boj 1976 - 여행가자

py solution

인덱싱 문제로 여러번 틀림. 첫 번째 값의 그룹을 구할 때에도 -1을 해주어야 한다는 것을 잊었다.

def solve():
    n = ria()[0]
    m = ria()[0]
    p = [-1]*(n+10)
    mat = []
    for r in range(n):
        mat.append(ria())

    path = ria()

    def find(k):
        if(p[k] < 0):
            return k
        p[k] = find(p[k])
        return p[k]

    def merge(a, b):
        A = find(a)
        B = find(b)
        if(A != B):
            p[B] = A

    for r in range(n):
        for c in range(n):
            if(mat[r][c] == 1):
                merge(r, c)

    firstValue = find(path[0]-1) # indexing 주의..

    for i, v in enumerate(path):
        if(find(v-1) != firstValue):
            print('NO')
            return
    print('YES')
    pass

boj 1806 - 부분합

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

투포인터 종료처리를 좀더 깔끔하게 생각하는 방법을 모르겠다. 아직을 볼 때마다 헷갈린다.

py solution

def solve():
    n, s = ria()
    curmin = 1000000009
    curminlen = 1000001
    cursum = 0
    arr = ria()
    diffs = [arr[0]]*(n+1)

    for i in range(n-1):
        diffs[i+1] = arr[i+1]-arr[i]
    it(diffs)

    right = 0
    left = 0
    cursum = 0
    # l~r 합 인덱싱을 어떻게 해야 깔끔하게 유지되나?
    # 같은 위치를 가리킬때 합이 0으로 생각
    # 0,0->0,   0,1->1

    while(True):
        # it(left, right, cursum)
        if(cursum >= s):
            curminlen = min(curminlen, right-left)
            curmin = min(curmin, cursum)
        if(cursum < s):
            if(right >= n):
                break
            cursum += arr[right]
            right += 1
        elif(cursum == s):
            if(right >= n):
                break
            if(left >= n):
                break
            cursum += arr[right]
            cursum -= arr[left]
            left += 1
            right += 1
        else:
            if(left >= n):
                break
            cursum -= arr[left]
            left += 1

    while(cursum >= s):
        # it(left, right, cursum)
        curminlen = min(curminlen, right-left)
        curmin = min(curmin, cursum)
        if(left >= n):
            break
        cursum -= arr[left]
        left += 1
    it(curmin, curminlen)
    if(curmin >= 1000000009):
        print(0)
        return
    print(curminlen)
    pass

boj 14868 - 문명

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

---