Coding 공부

import sys
from itertools import combinations
import math
def input():
    return sys.stdin.readline().rstrip()



N = int(input())

graph = [[] for _ in range(N+1)]


for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

d_cnt = 0
g_cnt = 0


for i in range(1,N+1):
    if len(graph[i])>=3:
        k = len(graph[i])
        cnt = math.factorial(k)/(math.factorial(3)*math.factorial(k-3))
        g_cnt += cnt
    if len(graph[i])>=2:
        for next_node in graph[i]:
            if len(graph[next_node])>=2:
                a = len(graph[i]) - 1
                b = len(graph[next_node]) - 1
                d_cnt += (a*b)

d_cnt//=2

if d_cnt > g_cnt*3:
    print('D')
elif d_cnt < g_cnt*3:
    print('G')
else:
    print('DUDUDUNGA')

ㅈ 을 그리는 방법은 해당 노드를 기준으로 자식노드가 3개이상이면 구할수 있따. 그러므로 자식노드 중 3개를 고르는 경우의 수를 더해주면 된다.

ㄷ을 그리는 방법은 다음과 같다. 서로 연결된 두 노드의 자식노드가 2개이상이어야할때이다.

왜냐하면 서로 연결이 되어 있으므로, 하나는 빼고 서로 다른 노드들의 개수를 곱해주면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def nC3(n):
    return (n*(n-1)*(n-2))//6

N = int(input())

graph_node_cnt = [0 for _ in range(N+1)]
edge_list = []
for _ in range(N-1):
    x,y = map(int,input().split())
    graph_node_cnt[x] += 1
    graph_node_cnt[y] += 1
    edge_list.append((x,y))

g_cnt = 0
d_cnt = 0
for node in range(1,N+1):
    if graph_node_cnt[node] >=3:
        g_cnt += nC3(graph_node_cnt[node])

for x,y in edge_list:
    if graph_node_cnt[x]>=2 and graph_node_cnt[y]>=2:
        d_cnt += (graph_node_cnt[x]-1)*(graph_node_cnt[y]-1)


if d_cnt>3*g_cnt:
    print('D')
elif d_cnt < 3*g_cnt:
    print('G')
else:
    print('DUDUDUNGA')

이건 팩토리얼 대신 사용한 것이다.

M,N = map(int,input().split())
def string_fun(num):
    temp = []
    for st in num:
        temp.append(num_st[int(st)])
    return ''.join(temp)
arr = []
for num in range(M,N+1):
    arr.append(str(num))

num_st = ['zero','one','two','three','four','five','six','seven','eight','nine']
arr.sort(key=string_fun)


for i in range(len(arr)//10):
    print(*arr[i*10:(i+1)*10])

if len(arr)%10:
    for i in range(len(arr)-len(arr)%10,len(arr)):
        print(arr[i],end=' ')

sort에 key를 줘서 정렬을 했다.

A,B = map(int,input().split())


if A>B:
    A,B = B,A

X,Y = map(int,input().split())
result = []
flag = True
if Y>=abs(X) or Y<0:
    flag = False
if flag:
    X = abs(X)
    value = X*(A//X)+Y
    while value<=B:
        if A<=value<=B:
            if result:
                flag = False
                break
            result.append(value)
        value += X
if flag and result:
    print(*result)
else:
    print('Unknwon Number')

  이 문제에서 주의해야할 점은 Y가 X보다 큰게 들어올수도 있으며, 0 미만일수도 있다.

그럴 경우엔 False를 해주고, A,B가 서로 반대로 들어올 수 있는것만 조심해주면 된다.

A~B 사이에서 생길수 있는 최소의 X,Y로 만들수 있는 수를 찾는다.

그리고 난뒤에 X를 늘려가면서, 2개이상의 수가 있을때에는 flag로 Unkwon Number를 출력해주면 된다.

A,B = map(int,input().split())


if A>B:
    A,B = B,A

X,Y = map(int,input().split())

X = abs(X)
left_div = A//X
right_div = (B+X)//X
result = []
flag = True
if Y>=abs(X) or Y<0:
    flag = False
if flag:
    for div in range(left_div,right_div+1):
        temp = div*X+Y
        if A<=temp<=B:
            if result:
                flag = False
                break
            else:
                result.append(temp)


if flag and result:
    print(*result)
else:
    print('Unknwon Number')

이건 반복문을 통해서 구현한 것이다.

import sys

input = sys.stdin.readline

def combination(ind,len_string,combi):
    if ind == len_string:
        print(combi)
    else:
        for k in range(len_string):
            if visited[k]:
                temp = combi+string_list[k]
                if temp not in record:
                    visited[k] = False
                    record.add(temp)
                    combination(ind+1,len_string,temp)
                    visited[k] = True 



N = int(input())

for _ in range(N):
    string_list = list(input().strip())
    string_list.sort()
    len_string = len(string_list)
    visited = [True]*(len(string_list))
    record = set()
    combination(0,len_string,'')

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

B,C = map(int,input().split())
answer = 0
for num in arr:
    num -= B
    answer += 1
    if num > 0:
        answer = answer + num//C + (0 if num%C == 0 else 1)
print(answer)

def gcd(A,B):
    if not A%B:
        return B
    return gcd(B,A%B)


N, M = map(int,input().split())
ab = M//N
list_a = []
last_N = int(ab**(1/2))
for number_a in range(last_N,0,-1):
    if not ab%number_a:
        number_b = ab//number_a
        if gcd(number_a,number_b) == 1:
            list_a.extend([number_a,number_b])
            break
print(*[ i*N for i in list_a])

M,N = map(int,input().split())
S = int(input())
# 북쪽 1 ==>0
# 남쪽 2 ==>N-1
# 서쪽 3 =>0
# 동쪽 4 => N-1
input_list = []
total_length = (N+M)*2
for tc in range(S+1):
    n1,n2 = map(int,input().split())
    if n1 == 1:
        input_list.append(n2)
    elif n1 == 2:
        input_list.append(M+N+(M-n2))
    elif n1 == 3:
        input_list.append(2*M+N+(N-n2))
    else:
        input_list.append(M+n2)

patrol = input_list[-1]
result = 0


for idx in range(S):
    temp = abs(input_list[idx]-patrol)
    result += min(temp,total_length-temp)
print(result) 

이 문제를 처음 풀때는 여러가지 경우로 나눌까 하다가, 생각해보니 이 문제는 직사각형의 테두리만 도는 것이고, 테두리의 둘레 값은 고정적이다. 그래서 한쪽만 구하면 반대편 값은 저절로 구해지는 것을 알수 있었다.

그래서 사각형을 하나의 직선 좌표로 바꾸었다.

순서는 북->동->남->서 순으로 (0,0) 좌표를 끊었다고 생각했을때 쭉 눌어지는 것처럼 했다.

위와 같은 직사각형을 밑과 같은 일직선으로 변경 후 두 점사이의 거리를 구했다.

전체 둘레에서 두 점사이의 거리를 뺀값과 두점 사이의 거리 중 더 짧은 것을 결과값에 더해주었다.