삼각달팽이

• 문제

• 해설

from math import sqrt

def n_to_total(n):
    # 4->10
    # 5->15
    # 6->21
    # n->n(n+1)/2
    return n*(n+1) // 2

def remains_to_edge_size(remains):
    # 1->1, 예외처리
    # 3->1
    # 6->2
    # 10->3
    # 15->4
    # 21->5
    # 28->6
    # 36->7
    # n(n+1)/2 -> n-1
    return round(((-1 + sqrt(1+8*remains))/ 2) - 1)

def edge_size_consumed(edge_size):
    return 3 * edge_size

def get_first(start_val, start_row_idx, start_col_idx, edge_size):
    return list(zip([*range(start_val, start_val + edge_size)], [*range(start_row_idx, start_row_idx + edge_size)], [start_col_idx]*(edge_size)))

def get_second(start_val, start_row_idx, start_col_idx, edge_size):
    return list(zip([*range(start_val+edge_size, start_val+2*edge_size)], [start_row_idx+edge_size] * edge_size, [*range(start_col_idx, start_col_idx + edge_size)]))

def get_third(start_val, start_row_idx, start_col_idx, edge_size):
    return list(zip([*range(start_val+2*edge_size, start_val+3*edge_size)], [*range(start_row_idx+edge_size, start_row_idx, -1)], [*range(start_col_idx+edge_size, start_col_idx, -1)]))

def solution(n):
    if n == 1:
        return [1]
    answer = [[0]*i for i in range(1, 1 + n)]
    funcs = [get_first, get_second, get_third]

    start_val = 1
    start_row_idx = 0  # increment : 2
    start_col_idx = 0  # increment : 1
    remains = n_to_total(n)
    edge_size = remains_to_edge_size(remains)    

    while (remains):
        for func in funcs:
            val_row_cols = func(start_val, start_row_idx, start_col_idx, edge_size)
            for val, row, col in val_row_cols:
                answer[row][col] = val
        consumed = edge_size_consumed(edge_size)
        start_val += consumed
        start_row_idx += 2
        start_col_idx += 1
        remains -= consumed
        edge_size = remains_to_edge_size(remains)
        if remains == 1:
            answer[start_row_idx][start_col_idx] = start_val
            remains -= 1

    answer = [x for sublist in answer for x in sublist]
    return answer

• 포인트
  • 각 삼각형을 외곽부터 layer-1, layer-2, …
  • 각 layer마다 세 개의 변으로 나눠 처리(왼쪽, 밑, 오른쪽을 first, second, third)
  • 이런 군수열방식이 아닌, 방향 개념 도입해서 풀면 더 간단할 듯

• 문제

• 해설

def get_rotation_candidates(mat, query):
    x1, y1, x2, y2 = query
    # (x, y, val)
    first = [(x1-1, y1 -1 + i, mat[x1-1][y1-1+i]) for i in range(y2-y1)]
    second = [(x1-1+i, y2-1, mat[x1-1+i][y2-1]) for i in range(x2-x1)]
    third = [(x2-1, y2-1-i, mat[x2-1][y2-1-i]) for i in range(y2-y1)]
    fourth = [(x2-1-i,y1-1, mat[x2-1-i][y1-1]) for i in range(x2-x1)]    
    return first, second, third, fourth

def get_min(first, second, third, fourth):
    return min(
        min(first, key=lambda x: x[2])[2],
        min(second, key=lambda x: x[2])[2], 
        min(third, key=lambda x: x[2])[2], 
        min(fourth, key=lambda x: x[2])[2], 
    )

def rotate(mat, first, second, third, fourth):
    mat[first[0][0]][first[0][1]] = fourth[-1][-1]
    mat[second[0][0]][second[0][1]] = first[-1][-1]
    mat[third[0][0]][third[0][1]] = second[-1][-1]
    mat[fourth[0][0]][fourth[0][1]] = third[-1][-1]

    if len(first) >= 2:
        for i in range(1, len(first)):
            new_val = first[i-1][-1]
            mat[first[i][0]][first[i][1]] = new_val
    if len(second) >= 2:
        for i in range(1, len(second)):
            new_val = second[i-1][-1]
            mat[second[i][0]][second[i][1]] = new_val
    if len(third) >= 2:
        for i in range(1, len(third)):
            new_val = third[i-1][-1]
            mat[third[i][0]][third[i][1]] = new_val
    if len(fourth) >= 2:
        for i in range(1, len(fourth)):
            new_val = fourth[i-1][-1]
            mat[fourth[i][0]][fourth[i][1]] = new_val    
    return mat

def solution(rows, columns, queries):
    init_mat = [[i for i in range(1 + (j-1)*columns, 1 + j * columns)] for j in range(1, 1 + rows)]
    mins = []
    for query in queries:
        first, second, third, fourth = get_rotation_candidates(init_mat, query)
        mins.append(get_min(first, second, third, fourth))
        init_mat = rotate(init_mat, first, second, third, fourth)
    return mins

• 포인트
  • min(listOfTuples, key=lambda x: x[2])[2] 을 통해 third element 최솟값 얻기
  • 테두리를 4분할해서 처리, 각 분할마다 첫점과 그 외를 나눠 해결

• 문제

• 해설

def calc_meet_x_y(line1, line2):
    A, B, E = line1
    C, D, F = line2
    AD_BC = A*D - B*C
    if AD_BC == 0:
        return None
    BF_ED = B*F - E*D
    EC_AF = E*C - A*F
    return (BF_ED)/(AD_BC), (EC_AF)/(AD_BC)

def isinteger(x):
    return int(x) == x

def transform_to_new_2d(point, max_min):
    x, y = point
    return x - max_min['min_x'], y - max_min['min_y']

def solution(line):
    max_min = {}
    met_points = []
    for outer_idx in range(len(line)):
        line1 = line[outer_idx]
        for inner_idx in range(outer_idx+1, len(line), 1):
            line2 = line[inner_idx]
            calc = calc_meet_x_y(line1, line2)
            if calc:
                x, y = calc
                if isinteger(x) and isinteger(y):
                    x, y = int(x), int(y)
                    if max_min.get('max_x', x) <= x:
                        max_min['max_x'] = x
                    if max_min.get('max_y', y) <= y:
                        max_min['max_y'] = y
                    if max_min.get('min_x', x) >= x:
                        max_min['min_x'] = x
                    if max_min.get('min_y', y) >= y:
                        max_min['min_y'] = y
                    met_points.append((x,y))


    outer_array_len = max_min['max_y'] - max_min['min_y'] + 1
    inner_array_len = max_min['max_x'] - max_min['min_x'] + 1

    answer = [["."]*inner_array_len for _ in range(outer_array_len)]
    for point in met_points:
        x, y = transform_to_new_2d(point, max_min)
        answer[y][x] = '*'
    answer = [''.join(row) for row in answer]
    return answer[::-1]

• 포인트
  • numeric x가 integer인지 확인은 int(x) == x
  • 계속 max_x, max_y, min_x, min_y를 추적하기
  • string은 immutable이니까 2d-array로 answer template 만들기(not 1d of str)

• 문제
  • 14501번: 퇴사
• 해결

import sys

resignation_day = sys.stdin.readline()

time_and_pay = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]

time_list = [x[0] for x in time_and_pay]
pay_list = [x[1] for x in time_and_pay]
cand = [0]

def go(time_list, pay_list, cur_ind, cumulative_pay):
    # 불가능
    if cur_ind >= len(time_list):
        return None

    # 정답
    if (cur_ind + time_list[cur_ind]) > len(time_list):
        if cand[0] < cumulative_pay:
            cand[0] = cumulative_pay
    if (cur_ind + time_list[cur_ind]) == len(time_list):
        if cand[0] < (cumulative_pay + pay_list[cur_ind]):
            cand[0] = cumulative_pay + pay_list[cur_ind]

    go(time_list, pay_list, cur_ind + time_list[cur_ind], cumulative_pay + pay_list[cur_ind])
    go(time_list, pay_list, cur_ind + 1, cumulative_pay)

    return cand[0]

print(go(time_list, pay_list, 0, 0))

• 포인트
  • Dynamic programming

• 문제
  • 14500번: 테트로미노
• 해결

import sys

height, width = [int(x) for x in sys.stdin.readline().split()]

mapping = [list(map(int, x.split())) for x in sys.stdin.readlines()]
case_to_sub = {
    0: 2,
    1: 1,
    2: 8,
    3: 4,
    4: 4
}

def case_sub_to_available(case, sub, total_row, total_col):
    if case == 0 and sub == 0:
        return total_row, total_col - 3, 0, 0
    elif case == 0 and sub == 1:
        return total_row - 3, total_col, 0, 0

    elif case == 1 and sub == 0:
        return total_row - 1, total_col - 1, 0, 0

    elif case == 2 and sub == 0:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 1:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 2 and sub == 2:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 3:
        return total_row - 1, total_col - 2, 1, 0

    elif case == 2 and sub == 4:
        return total_row - 2, total_col - 1, 2, 0
    elif case == 2 and sub == 5:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 2 and sub == 6:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 7:
        return total_row - 1, total_col - 2, 0, 0

    elif case == 3 and sub == 0:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 3 and sub == 1:
        return total_row - 1, total_col - 2, 1, 0

    elif case == 3 and sub == 2:
        return total_row - 2, total_col - 1, 1, 0
    elif case == 3 and sub == 3:
        return total_row - 1, total_col - 2, 0, 0

    elif case == 4 and sub == 0:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 4 and sub == 1:
        return total_row - 2, total_col - 1, 1, 0
    elif case == 4 and sub == 2:
        return total_row - 1, total_col - 2, 1, 0
    elif case == 4 and sub == 3:
        return total_row - 2, total_col - 1, 0, 0

def get_val(case, sub, r, c, d):
    if case == 0 and sub == 0:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r][c + 3]
    elif case == 0 and sub == 1:
        return d[r][c] + d[r + 1][c] + d[r + 2][c] + d[r + 3][c]

    elif case == 1 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r][c + 1] + d[r + 1][c + 1]

    elif case == 2 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r + 2][c] + d[r + 2][c + 1]
    elif case == 2 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c]
    elif case == 2 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r + 1][c + 1] + d[r + 2][c + 1]
    elif case == 2 and sub == 3:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r - 1][c + 2]

    elif case == 2 and sub == 4:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r - 2][c + 1]
    elif case == 2 and sub == 5:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c + 2]
    elif case == 2 and sub == 6:
        return d[r][c] + d[r][c + 1] + d[r + 1][c] + d[r + 2][c]
    elif case == 2 and sub == 7:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 1][c + 2]

    elif case == 3 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 2][c + 1]
    elif case == 3 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r - 1][c + 2]
    elif case == 3 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r + 1][c]
    elif case == 3 and sub == 3:
        return d[r][c] + d[r][c + 1] + d[r + 1][c + 1] + d[r + 1][c + 2]

    elif case == 4 and sub == 0:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c + 1]
    elif case == 4 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r + 1][c + 1]
    elif case == 4 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r - 1][c + 1]
    elif case == 4 and sub == 3:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 2][c]

max_ = 0
for case in case_to_sub.keys():
    for sub in range(case_to_sub[case]):
        row_cnt, col_cnt, start_row, start_col = case_sub_to_available(case, sub, height, width)
        for r in range(start_row, start_row + row_cnt, 1):
            for c in range(start_col, start_col + col_cnt, 1):
                val = get_val(case, sub, r, c, mapping)
                if val > max_:
                    max_ = val
print(max_)

• 포인트
  • Bruteforce
  • 모든 도형마다 가능한 좌우대칭 경우를 생성

• 문제
  • 13023번: ABCDE
• 해결

import sys

person_count, relation_count = [int(x) for x in sys.stdin.readline().strip().split()]

data = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]

relation = {k: [] for k in range(person_count)}

for x in data:
    relation[x[0]].append(x[1])
    relation[x[1]].append(x[0])

relation = {k: set(v) for k, v in relation.items()}

for k in relation.keys():
    for i in relation[k] - set([k]):
        for j in relation[i] - set([k, i]):
            for u in relation[j] - set([k, i, j]):
                if len(relation[u] - set([k, i, j, u])):
                    print(1)
                    exit()
print(0)

• 포인트
  • 길이가 5인 path의 존재인 문제인데 길이가 5로 고정되어 네번의 for-loop로 해결
  • dfs로 길이가 5되는 것 찾아도 될 듯

• 문제
  • 11724번: 연결 요소의 개수
• 해결

import sys

sys.setrecursionlimit(99999)

vertex_count, edge_count = [int(x) for x in sys.stdin.readline().strip().split()]

edges = [list(map(int, each.strip().split())) for each in sys.stdin.readlines()]

adj_list = [[] for _ in range(vertex_count + 1)]
chk_list = [False] * (vertex_count + 1)
connected_components = []

for each in edges:
    adj_list[each[0]].append(each[1])
    adj_list[each[1]].append(each[0])

for v in range(1, len(adj_list)):
    adj_list[v] = sorted(list(set(adj_list[v])))

def dfs(vertex, connected_component):
    chk_list[vertex] = True
    connected_component.append(vertex)
    for neighbor in adj_list[vertex]:
        if not chk_list[neighbor]:
            dfs(neighbor, connected_component)

for vertex in range(1, len(adj_list)):
    if not chk_list[vertex]:
        connected_component = []
        dfs(vertex, connected_component)
        connected_components.append(connected_component)

print(len(connected_components))

• 포인트
  • dfs

• 문제
  • 10972번: 다음 순열
• 해설

import sys

N = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

def next_permutation(list_):
    get_i = 0
    for i in range(len(list_)-1):
        if list_[i] < list_[i+1]:
            get_i = i

    get_j = 0
    for j in range(get_i+1, len(list_), 1):
        if list_[get_i] < list_[j]:
            get_j = j

    if get_i == 0 and get_j == 0:
        return False
    else:
        list_[get_i], list_[get_j] = list_[get_j], list_[get_i]
        get_j = len(list_)-1
        while (get_i+1 < get_j):
            list_[get_i+1], list_[get_j] = list_[get_j], list_[get_i+1]
            get_i += 1; get_j -= 1
        return True

if next_permutation(data):
    res = [str(x) for x in data]
    res = ' '.join(res)
    print(res)
else:
    print(-1)

• 포인트
  • next permutation은 증가조짐인 가장 오른쪽놈(i)와 (i)의 오른쪽놈들 중 (i)보다 큰놈 중 가장 작은 놈(=큰놈 중 가장 오른쪽 놈)(j)을 교체하는 것

• 문제
  • 10819번: 차이를 최대로
• 해결

import sys

N = sys.stdin.readline()
data = list(map(int, sys.stdin.readline().split()))

data.sort()

def next_permutation(list):
    last_asc_idx = 0
    for i in range(len(list) - 1):
        if list[i] < list[i + 1]:
            last_asc_idx = i

    val_at_last_asc_idx = list[last_asc_idx]
    last_idx_larger_than_val_at_last_asc_idx = 0
    for j in range(last_asc_idx + 1, len(list), 1):
        if val_at_last_asc_idx < list[j]:
            last_idx_larger_than_val_at_last_asc_idx = j

    if last_asc_idx == 0 and last_idx_larger_than_val_at_last_asc_idx == 0:
        return False
    else:
        list[last_asc_idx], list[last_idx_larger_than_val_at_last_asc_idx] = \\
            list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx]
        last_idx_larger_than_val_at_last_asc_idx = len(list) - 1
        while last_asc_idx + 1 < last_idx_larger_than_val_at_last_asc_idx:
            list[last_asc_idx + 1], list[last_idx_larger_than_val_at_last_asc_idx] = \\
                list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx + 1]
            last_asc_idx += 1;
            last_idx_larger_than_val_at_last_asc_idx -= 1
        return True

def get_res(list):
    res = 0
    for i in range(len(list) - 1):
        if list[i] < list[i + 1]:
            res += list[i + 1] - list[i]
        else:
            res += list[i] - list[i + 1]
    return res

max_res = get_res(data)
while next_permutation(data):
    tmp_res = get_res(data)
    if max_res < tmp_res:
        max_res = tmp_res

print(max_res)

• 포인트
  • bruteforce 파악

• 문제
  • 9613번: GCD 합
• 해결

import sys

test_case_count = int(sys.stdin.readline())

def get_gcd(m, n):
    if n > m:
        m, n = n, m
    if n == 0:
        return m
    else:
        return get_gcd(n, m % n)

for i in range(test_case_count):
    numbers = [int(x) for x in sys.stdin.readline().split()][1:]
    res = 0
    for j in range(0, len(numbers) - 1, 1):
        for k in range(1, len(numbers) - j, 1):
            res += get_gcd(numbers[j], numbers[j + k])
    print(res)

• 포인트
  • 쉬움