나를 잃지 말자

• 문제
  • 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)

• 포인트
  • 쉬움

• 문제
  • 9095번: 1, 2, 3 더하기
• 해결

import sys

test_case_count = int(sys.stdin.readline())
target_numbers = [int(x.strip()) for x in sys.stdin.readlines()]

def go(target, cumulative_sum):
    res = 0
    # 불가능한 경우
    if cumulative_sum > target:
        return 0

    # 정답을 찾은 경우
    if cumulative_sum == target:
        return 1

    # 계속 호출하는 경우
    if cumulative_sum < target:
        for i in [1, 2, 3]:
            res += go(target, cumulative_sum + i)
    return res

for target in target_numbers:
    print(go(target, 0))

• 포인트
  • recursive

• 문제
  • 6603번: 로또
• 해결

import sys

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

def go(current_list, remainder_list):
    # 로또 번호를 여섯개 이상 넣은 경우
    if len(current_list) > 6:
        return None

    # 여섯개 추첨
    if len(current_list) == 6:
        print(' '.join([str(x) for x in current_list]))

    # 아직 숫자가 모자르면
    if 0 <= len(current_list) < 6:
        # 남은 숫자가 있다면
        if len(remainder_list):
            for idx, val in enumerate(remainder_list):
                go(current_list + [val], remainder_list[(idx + 1):])

for ind, list_ in enumerate(data):
    if list_[0] == 0:
        exit()
    else:
        if ind != 0:
            print(' ')
        go([], list_[1:])

• 포인트
  • 첫 번호을 기준으로 dynamic programming

• 문제
  • 6588번: 골드바흐의 추측
• 해설

import sys

data = [int(x.strip()) for x in sys.stdin.readlines()][:-1]

def prime_candidate_generator_less_than(n):
    # 3, 5, 7, 11, 13, 17, 19, ...
    yield 2
    yield 3
    candidate = 5
    increment = 2
    increment_changer = {2: 4, 4: 2}
    while candidate <= n:
        yield candidate
        candidate += increment
        increment = increment_changer[increment]

def get_primes_by_sieve_less_than(n):  # n >= 6
    prime_list = []
    sieve_list = [True] * (n + 1)
    for candidate in prime_candidate_generator_less_than(n):
        if sieve_list[candidate]:
            prime_list.append(candidate)
            for i in range(2, 1 + (n // candidate)):
                sieve_list[candidate * i] = False
    return prime_list, sieve_list

prime_list, sieve_list = get_primes_by_sieve_less_than(max(data))
for i in data:
    for j in prime_list:
        if sieve_list[i - j]:
            print("{0} = {1} + {2}".format(i, j, i - j))
            break

• 포인트
  • 에라토스테네스의 체
  • 가장 큰 n에 대해서 체를 한번만 이용하기

• 문제
  • 4963번: 섬의 개수
• 해설

import sys

sys.setrecursionlimit(99999)

def get_data():
    width, height = [int(x) for x in sys.stdin.readline().split()]
    if height == 0:
        sys.exit()
    mapping = []
    for x in range(height):
        mapping.append([int(z) for z in sys.stdin.readline().split()])
    return width, height, mapping

def chk_in_map(x, y, mapping):
    return 0 <= x < len(mapping) and 0 <= y < len(mapping[0])

dx_list = [-1, 0, 1]
dy_list = [-1, 0, 1]

def dfs(x, y, chk, mapping, ans):
    chk[x][y] = True
    ans += 1
    for dx in dx_list:
        for dy in dy_list:
            if dx == 0 and dy == 0:
                continue
            cand_x = x + dx
            cand_y = y + dy
            if chk_in_map(cand_x, cand_y, mapping) and mapping[cand_x][cand_y] == 1 and not chk[cand_x][cand_y]:
                dfs(cand_x, cand_y, chk, mapping, ans)
    return ans

for _ in range(999999999):
    ans = 0
    width, height, mapping = get_data()
    chk = [[False for z in range(width)] for q in range(height)]
    for x in range(height):
        for y in range(width):
            if mapping[x][y] and not chk[x][y]:
                ans = dfs(x, y, chk, mapping, ans)
    print(ans)

• 포인트
  • dfs

• 문제
  • 2667번: 단지번호붙이기
• 해설

import sys

sys.setrecursionlimit(99999)

size = int(sys.stdin.readline().strip())
mapping = [[0] * size for x in range(size)]

for i, x in enumerate(sys.stdin.readlines()):
    for j, y in enumerate(x.strip()):
        mapping[i][j] = int(y)

went_or_not = [[False for _ in range(size)] for _ in range(size)]

def is_in_map(x, y):
    return 0 <= x < size and 0 <= y < size

def dfs(x, y, res):
    went_or_not[x][y] = True
    candidates = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
    for nx, ny in candidates:
        if is_in_map(nx, ny):
            if mapping[nx][ny] and not went_or_not[nx][ny]:
                res.append(1)
                dfs(nx, ny, res)
    return res

final_res = []
for x in range(size):
    for y in range(size):
        if mapping[x][y] != 0 and went_or_not[x][y] == False:
            res_ = dfs(x, y, [1])
            if len(res_) >= 1:
                final_res.append(len(res_))
final_res = sorted(final_res)
print(len(final_res))
for x in final_res:
    print(x)

• 포인트
  • dfs로 풀 생각
  • 각 단지안에 집 개수도 세야하니까 안가본(went_or_not이 False) 그리고 집(mapping에서 1)에서 시작하면서 list를 인자로 받아 늘리기

• 문제
  • 2609번: 최대공약수와 최소공배수
• 해설

import sys

m, n = list(map(int, sys.stdin.readline().split()))
if n > m:
    m, n = n, m

def get_gcd(a, b):
    if b == 0:
        return a
    else:
        return get_gcd(b, a % b)

gcd = get_gcd(m, n)
print(get_gcd(m, n))
print(int((m * n) / gcd))

• 포인트
  • 유클리드 호제법

• 문제
  • 2309번: 일곱 난쟁이
• 해설

import sys

nine_heights = [int(x) for x in sys.stdin.readlines()]
nine_sum = sum(nine_heights)
is_done = False

for left_idx in range(8):
    for right_idx in range(left_idx + 1, 9, 1):
        if (nine_sum - nine_heights[left_idx]) - nine_heights[right_idx] == 100:
            ans = sorted([x for ind, x in enumerate(nine_heights) if ind != left_idx and ind != right_idx])
            for k in ans:
                print(k)
            is_done = True
            break
    if is_done:
        break

• 포인트
  • 왼쪽에서 모든 경우 다 헤아리기

• 문제
  • 2178번: 미로 탐색
• 해설

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)

N, M = [int(x) for x in sys.stdin.readline().strip().split()]
maze = [list(map(int, x.strip())) for x in sys.stdin.readlines()]

queue = deque()
dx_dy = [(-1, 0), (1, 0), (0, 1), (0, -1)]
went_or_not = [[False for y in range(M)] for x in range(N)]

def can_go(x, y):
    if 0 <= x < N and 0 <= y < M and maze[x][y] and not went_or_not[x][y]:
        return True
    else:
        return False

def is_destination(x, y):
    return x == (N - 1) and y == (M - 1)

ans = [N * M]

def bfs(x, y, cnt):
    went_or_not[x][y] = True
    cnt += 1
    for diff in dx_dy:
        ax, ay = [sum(z) for z in zip((x, y), diff)]
        if can_go(ax, ay):
            went_or_not[ax][ay] = True
            if is_destination(ax, ay):
                ans[0] = ans[0] if ans[0] < cnt else cnt
            else:
                queue.appendleft((ax, ay, cnt))
    if len(queue):
        ax, ay, cnt = queue.pop()
        bfs(ax, ay, cnt)

bfs(0, 0, 1)
print(ans[0])

• 포인트
  • bfs문제