Coding 공부

N, M = map(int,input().split())
total_length = N*M
so_list = [M]*N

cnt = 0
for k in range(N):
    if so_list[k]%N:
        cnt += so_list[k]//N
    else:
        cnt = cnt + so_list[k]//N-1
    so_list[k] -= so_list[k]//N*N

if sum(so_list):
    ind = 0
    temp = 0
    while ind <N:
        temp += so_list[ind]
        if temp == N:
            temp = 0
        elif temp >N:
            cnt += 1
            temp -= N
        ind += 1
        
print(cnt)

import functools
n,m = map(int,input().split())
@functools.lru_cache()
def gdc(n,m):
    if not n%m:
        return m
    return gdc(m,n%m)

print(m-gdc(n,m))

def solution(ind,diff):
    if diff > 250000:
        return -INF
    if ind == N:
        if diff == 0:
            return 0
        else:
            return -INF
    if dp[ind][diff] != -1:
        return dp[ind][diff]

    dp[ind][diff] = solution(ind+1,diff+arr[ind])
    dp[ind][diff] = max(dp[ind][diff],solution(ind+1,diff))
    if arr[ind] > diff:
        dp[ind][diff] = max(dp[ind][diff],diff + solution(ind+1,arr[ind]-diff))
    else:
        dp[ind][diff] = max(dp[ind][diff],arr[ind] + solution(ind+1,diff-arr[ind]))
    return dp[ind][diff]

N = int(input())
arr = list(map(int,input().split()))
arr = arr + [0]
INF = float('inf')
dp = [[-1] * 500001 for _ in range(N+1)]

result = solution(0,0)
if result == 0:
    print(-1)
else:
    print(result)

힘들게 풀었던 문제이다.

dp의 테이블에서 행은 현재의 index를 말하며, 열은 두 탑의 격차의 절대값을 말한다.

재귀함수를 통해 짰는데.

첫번째 : 해당 블록을 높이가 더 높은 쪽에 놓았을때,

두번째 : 해당 블록을 놓지 않았을때

세번째 : 높이가 낮은 블록에 놓았을 때 : 이 때 주의해야할 것은 현재 공통적으로 쌓아올려진 높이는 diff와 arr[ind]의 두 크기 중 작은 것에 된다.

이렇게 3가지 경우로 나뉘며, 세번째에는 격차가 클때와 현재 블록이 클때로 나뉘어서 된다.

이렇게 재귀를 하면서 마지막에서 들어온 diff가 0이면 높이가 같은것이므로 0을 반환해주고, 그게 아니면 두 높이가 다른것이므로, -INF를 반환해준다.

이게 내 첫번째 풀이였고, 실행시간은 3900ms로 엄청 느렸다.

그래서 다른 사람 풀이를 보고 공부한 코드는 다음과 같다.

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))

if N == 1:
    print(-1)
else:
    total_sum = sum(arr)
    dp = [[-1] * total_sum for _ in range(N)]
    dp[0][0] = 0
    dp[0][arr[0]] = arr[0]
    for ind in range(N-1):
        for j in range(total_sum//2+1):
            if dp[ind][j] != -1:
                # 다음 거의 블록을 쓰지 않을때
                dp[ind+1][j] = max(dp[ind][j],dp[ind+1][j])
                # 두 탑 중 더 높은 탑쪽에 블록을 쌓을때
                if j + arr[ind+1] < total_sum:
                    dp[ind+1][j+arr[ind+1]] = max(dp[ind+1][j+arr[ind+1]],dp[ind][j]+arr[ind+1])
                # 더 낮은 탑 쪽에 쌓는데 새로 쌓는 블록이 기존 블록보다 높을때 와 아닐때
                if arr[ind+1] > j:
                    dp[ind+1][arr[ind+1]-j] = max(dp[ind+1][arr[ind+1]-j],dp[ind][j] + arr[ind+1]-j)
                else:
                    dp[ind+1][j-arr[ind+1]] = max(dp[ind+1][j-arr[ind+1]],dp[ind][j])
    if dp[-1][0] == 0:
        print(-1)
    else:
        print(dp[-1][0])

위와 dp 테이블은 동일하다. 그런데 전체 input의 합을 구하고, 그거의 반만큼만 반복을 돌리도록 했다.

그래서 위에서는 재귀를 통해서 돌아가다 보니, 무조건 3개의 함수가 실행되다보니 밑의 코드보다 훨씬 오래걸린다.

밑의 코드는 50*250000이 최대 횟수로 볼수 있으므로, 위의 것보다 연산량에 이득을 본것 같다.

여기도 위와 비슷하게,

아무것도 놓지 않았을때

두 탑 중 더 높은 탑쪽에 쌓았을때,

두 탑 중 더 낮은 탑쪽에 쌓았을때,

를 구분해서 놓으면 된다.

그리고 dp에 저장되는 값은 해당 index에서 두 탑의 높이가 diff만큼 차이가 날때, 그때 더 높은탑의 크기를 저장해놓는 것이므로,

그것을 잘 구분해서, dp에 저장시켜주면 된다.

N = int(input())
arr = list(map(int,input().split()))

num_cnt = [0]*1005

for num in arr:
    num_cnt[num] += 1


cur = 0
result = []
while sum(num_cnt)>0:
    if num_cnt[cur]:
        if num_cnt[cur+1]:
            for next_num in range(cur+2,1001):
                if num_cnt[next_num]:
                    result.extend(num_cnt[cur]*[cur])
                    result.append(next_num)
                    num_cnt[cur] = 0
                    num_cnt[next_num] -= 1
                    break
            else:
                result.extend(num_cnt[cur+1]*[cur+1])
                result.extend(num_cnt[cur]*[cur])
                num_cnt[cur] = 0
                num_cnt[cur+1] = 0

        else:
            while num_cnt[cur]:
                result.append(cur)
                num_cnt[cur] -= 1
    cur += 1

print(*result)

플래티넘 문제로 어려웠던 문제였다. 

이 문제를 푸는 방법은 구분을 하는 것이다.

현재 숫자를 CUR이라고 하겠다. CUR+1의 숫자가 있는 경우와 없을때를 비교를 해서, 정렬을 해주면된다.

만약 CUR + 1의 숫자가 없을때에는 CUR의 값을 전부 출력시키면 된다.

그러나 CUR+1의 값이 존재할때는 2가지 경우가 있다.

CUR 보다 2이상 큰 값들이 존재하는지와 없는지 이다.

만약 없을때에는 CUR+1의 값들을 전부 출력한뒤에 CUR 값들을 출력시키면 된다.

그게 아니라 CUR보다 2이상 큰 값이 존재를 한다면,

CUR의 값들을 전부 출력시키고 그 다음에 CUR보다 2이상 큰 값을 한개 출력해주면 된다.

그러면 CUR과 CUR+1 사이에 CUR+2(이상)의 값이 들어가줘서 문제의 조건대로 출력이 가능해진다.

from itertools import combinations

N,K = map(int,input().split())
ord_dict = {}
if K <5:
    print(0)
    exit()
elif K == 26:
    print(N)
    exit()
else:
    # 2**승으로 만들어 주기 위한 곳
    for k in range(26):
        ord_dict[chr(k+97)] = k

    K = K - 5
    comb_bits = 0
    # 무조건 있는 애들을 기본적으로 comb_bits로 만들어준다.
    for k in ['a','n','t','i','c']:
        comb_bits = comb_bits + 2**ord_dict[k]
    word_list = []


    for _ in range(N):
        # 앞뒤 고정 부분은 필요없으니 자른다.
        temp = set(list(input())[4:-4])
        word_list.append(temp)
    # 고정적으로 잇는 부분 제외하고 나머지를 뽑는다.
    combi_word = set(ord_dict.keys()) - set(['a','n','t','i','c'])
    result = 0
    for pick_words in combinations(combi_word,K):
        check_bits = comb_bits
        for pick_word in pick_words:
            # OR 연산을 해줘서 BIT 형식으로 만들어준다.
            check_bits = check_bits | 1<< ord_dict[pick_word]

        word_cnt = 0
        for word in word_list:
            for wo in word:
                # 만약에 AND 연산을 했는데 False가 나오면 그만둔다.
                if not (check_bits & 1<<ord_dict[wo]):
                    break
            else:
                word_cnt += 1
        result = max(word_cnt,result)
                
    print(result)

어렵지 않은 문제인데 python을 이용해서 풀려면 참 난감해진 문제였다. 조합을 잘 짜면, 시간을 넘지않을수도 있지만, 

시간초과에 걸리는 경우가 많았다.

그래서 조합을 구하는 방식을 비트마스킹을 통해 만들었따. 2**(k)승의 형태로 만들어주고, and 연산을 해서 우리가 만든 조합에 포함되어있는지 아닌지 확인하는 방식이다.

from itertools import combinations

N,K = map(int,input().split())
ord_dict = {}

for k in range(26):
    ord_dict[chr(k+97)] = k

K = K - 5
if K <0:
    print(0)
    exit(0)
else:
    origin_word = set(['a','n','t','i','c'])
    word_bit_list = list()
    combination_word = set()
    answer = 0
    for _ in range(N):
        temp = set(list(input())[4:-4]) - origin_word
        if len(temp) == 0:
            answer += 1
        elif len(temp) <=K:
            word_bit = 0
            for w in temp:
                word_bit = word_bit + 2**ord_dict[w]
            word_bit_list.append(word_bit)
            combination_word |= temp

    word_lens = len(combination_word)
    if K > word_lens:
        K = word_lens
    chk_cnt = 0
    for pick_words in combinations(combination_word,K):
        cnt = 0
        temp = 0
        for pick_word in pick_words:
            temp = temp + 2**ord_dict[pick_word]
        for word_bit in word_bit_list:
            if word_bit & temp == word_bit:
                cnt += 1

        chk_cnt = max(chk_cnt,cnt)

    print(answer + chk_cnt)

위의 방식보다 훨씬 빠른 방식이다. 이 방식은 기본적인 컨셉은 비슷하다.

하지만 2가지가 다르다.

첫번째는 전체 알파벳 26개중에서 K개를 뽑던거에서 고정적으로 들어간 a,c,i,n,t를 무조건 뽑는다고 생각하고,

그리고 주어진 단어들에 있는 단어들 중에서 나머지 K-5개를 뽑는것이다.

두번째는 각 단어들의 BIT를 비교했던것에서 단어 전체의 bit를 저장해준뒤, 우리가 만든 combination bit와 and 연산을해서, 원래 word_bit가 유지되는지 확인을 해주는 방식이다.

이러한 방법을 통해 시간을 줄일 수 있다.

어제 결국 플레 5를 달성했다..

플레4는 그냥 꿈만 꾸는걸로

import sys

sys.setrecursionlimit(1000)
def dfs(node,cnt):
    for next_node,val in enumerate(arr[node]):
        if val and visited[next_node] == 0:
            visited[next_node] = cnt
            dfs(next_node,cnt)





N = int(input())
M = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]

tour_list = list(map(int,input().split()))

visited = [0]*N
cnt = 1
for i in range(N):
    if visited[i] == 0:
        visited[i] = cnt
        dfs(i,cnt)
        cnt += 1

result = 'YES'
init = visited[tour_list[0]-1]
for city in tour_list[1:]:
    if visited[city -1] != init:
        result = 'NO'
print(result)

첫 풀이 방식은 다음과 같았다.

DFS를 통해 모두 연결이 된대를 같은 cnt로 표시를 했다. 그런데 만약에 같은 cnt가 아니라면 tour_list에서 한번에 갈수 없는 곳 이므로 result를 No로 출력했다.

import sys
input = sys.stdin.readline

def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x
    for i in range(N+1):
        if make_set[i] != i:
            make_set[i] = find_parent(make_set[i])

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
     
    return find_parent(make_set[ind])
N = int(input())
M = int(input())
edges = []
for i in range(N):
    graph_list = list(map(int,input().split()))
    for j in range(N):
        if graph_list[j] == 1:
            edges.append((i+1,j+1))

tour_list = list(map(int,input().split()))
make_set = [i for i in range(N+1)]

for edge in edges:
    node_a,node_b = edge
    if find_parent(node_a) != find_parent(node_b):
        union(node_a,node_b)

init_value = make_set[tour_list[0]]
result = 'YES'
for city in tour_list:
    if init_value != make_set[city]:
        result = 'NO'
        break
print(result)

좀 더 원론적인 union find를 해서 같은 집합인지 아닌지 판별을 했다.

그리고 난뒤에 같은 집합이 아니면 No를 출력하게 했다.

# 7576번 문제 
# 1은 익은 토마토 0은 익지않은 토마토

N,M = map(int,input().split())

tomatoarray = [list(map(int,input().split())) for _ in range(M)]

dx = [-1,1,0,0]
dy = [0,0,1,-1]
tomatocnt = 0
total = N*M
tomato = []
for x in range(M):
    for y in range(N):
        if tomatoarray[x][y] == 1:
            tomato.append((x,y))
            tomatocnt += 1
        elif tomatoarray[x][y] == -1:
            total -= 1
result = -1
day = 0
if total == tomatocnt:
    result = 0
else:
    while tomato:
        new_tomato = []
        for x,y in tomato:
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<M and 0<=ny<N:
                    if not tomatoarray[nx][ny]:
                        tomatoarray[nx][ny] = 1
                        new_tomato.append((nx,ny))
                        tomatocnt += 1


        day += 1
        if tomatocnt == total:
            result = day
            break
        if len(new_tomato):
            tomato = [row[:] for row in new_tomato]
        else:
            result = -1
            break



print(result)

BFS를 활용해 day별로 새로 토마토가 된 곳을 찾아서 해주었다. 

N,K = map(int,input().split())

number =list(input())


result = [number[0]]
idx = 1
while K and idx <N:
    while result and K and number[idx] > result[-1]:
        result.pop()
        K -= 1
    result.append(number[idx])
    idx += 1
for _ in range(K):
    result.pop()
result = result + number[idx:]
print(''.join(result))

기본적인 원리는 다음과 같다.

반복문을 돌리면서 result에 마지막수보다 새로들어온 값이 클시에는 그 값들을 하나씩 빼준다. 그리고 난뒤 append를 해준다.

이렇게 끝까지 갔는데도, K가 남아있을시에는 남은 K만큼 pop을 해준다.

그리고, 만약 끝까지 가지 않았는데도, K만큼의 수를 이미 뺐다하면, 나머지 값들을 뒤에 붙여주면 된다.