log 2021-09-11

---

• sport
  • bj 1051
  • bj 11663
  • bj 1309 - 동물원

sport

유형별 쉬운 문제풀기

bj 1051

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

구현 문제

py solution

def solve():
    n,m=ria()
    maps=create2DArray(n,m,0)
    for row in range(n):
        maps[row]=list(map(int, list(rsa()[0])))
    
    md = min(n,m)
    
    best = -1
    for d in range(0,md):
        for sr in range(n-d):
            for sc in range(m-d):
                nr = sr+d
                nc = sc+d

                # print('d',d,'sr',sr,'sc',sc,'nr',nr,'nc',nc)
                
                fail=False
                ch = maps[sr][sc]
                if(ch != maps[sr][nc]):
                    fail=True
                elif(ch != maps[nr][sc]):
                    fail=True
                elif(ch != maps[nr][nc]):
                    fail=True
                # print('fail',fail, 'd', d)
                if not fail:
                    best = max(best, d)
    print((best+1)**2)
    
    pass

bj 11663

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

py solution

def solve():
    n,m = ria()
    dots = ria()
    dots.sort()
    
    for mm in range(m):
        start,end = ria()
        
        # search start idx
        ss = -1
        ee = n
        target = start
        while(ss+1<ee):
            mid=int((ss+ee)/2)
            if(target <= dots[mid]):
                ee = mid
            else:
                ss = mid
        # print('ee', ee)
        start_idx = ee

        # search end idx
        ss = -1
        ee = n
        target = end
        while(ss+1<ee):
            mid=int((ss+ee)/2)
            if(target < dots[mid]):
                ee = mid
            else:
                ss = mid

        end_idx = ee

        # print('start', start_idx, 'end', end_idx)
        print(end_idx-start_idx)
    
    
    pass

bj 1309 - 동물원

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

py solution

def solve():
    MOD = 9901
    N = ria()[0]
    dp = create2DArray(N, 3, -1)
    dp[0][0] = 1
    dp[0][1] = 1
    dp[0][2] = 1
    def dfs(r, k):
        if(dp[r][k]!=-1):
            return dp[r][k]
        
        ret = 0
        if(k == 0):
            ret = dfs(r-1, 1) + dfs(r-1, 2)
        elif(k == 1):
            ret = dfs(r-1, 0) + dfs(r-1, 2)
        else:
            ret = dfs(r-1, 0) + dfs(r-1, 1) + dfs(r-1, 2)
        ret %= MOD
        dp[r][k] = ret
        return ret
    
    ans = (dfs(N-1,0) + dfs(N-1,1) + dfs(N-1,2)) % MOD
    print(ans)
    
    pass

---