Jinho Tech

단순 수학 문제이다. 9501번 꿍의 우주여행과 같은 문제이다.

for _ in range(int(input())):
    N, D = map(int, input().split())
    cnt = 0
    for i in range(N):
        v, f, c = map(int, input().split())
        if v * f/c >= D:
            cnt += 1
    print(cnt)

단순한 수학 문제이다. N이 4의 배수이면 짝수, N이 2의 배수이면 홀수, N이 홀수이면 짝수, 홀수 둘다 가능하다.

N = int(input())
if N%4 == 0:
    print("Even")
elif N%2 == 0:
    print("Odd")
else:
    print("Either")

단순한 자료 구조 문제이다. 딕셔너리(해시)로 풀었다.

a, b = map(int, input().split())
A, B = {}, {}
for n in map(int, input().split()):
    A[n] = 1
for n in map(int, input().split()):
    B[n] = 1
cnt = 0
res = []
for n in A:
    if n not in B:
        cnt += 1
        res.append(n)
print(cnt)
if cnt:
    print(*sorted(res))

딕셔너리(해시)로 풀었다. 공통된 문자열이 개수를 구하면 되는 문제다.

import sys
input = sys.stdin.readline

n = int(input())
d1, d2 = {}, {}
for _ in range(n):
    s = input()
    d1[s] = d1.get(s, 0) + 1
for _ in range(n):
    s = input()
    d2[s] = d2.get(s, 0) + 1
res = 0
for t in d1.keys():
    if t in d2:
        res += min(d1[t], d2[t])
print(res)

그냥 백트래킹 형식으로 쉽게 풀었다. 

def dfs(depth):
    if depth == k:
        s.add(''.join(map(str, li)))
        return ;
    for i in range(n):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0
        
n, k = int(input()), int(input())
nums = [int(input()) for _ in range(n)]
li, s = [], set()
check = [0]*n
dfs(0)
print(len(s))

기본적인 스택 문제이다.

import sys
input = sys.stdin.readline

N = int(input())
li = [int(input()) for _ in range(N)]
stack, cnt = [li.pop()], 1
for n in li[::-1]:
    if stack[-1] < n:
        cnt += 1
        stack.append(n)
print(cnt)

기본적인 백트래킹 문제이다. 15663번 N과 M (9)와 비슷한 문제이다.

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        if depth == 0 or li[-1] <= nums[i]:
            li.append(nums[i])
            dfs(depth+1)
            li.pop()

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
dfs(0)

기본적인 백트래킹 문제이다. 15663번 N과 M (9)와 비슷한 문제이다.

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        li.append(nums[i])
        dfs(depth+1)
        li.pop()

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
dfs(0)

기본적인 백트래킹 문제이다. 15663번 N과 M (9)과 비슷한 문제이다. 

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, N):
            check[j] = 0

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
check = [0]*N
dfs(0)

기본적인 백트래킹 문제이다. 그냥 리스트를 사용해서 중복인지 아닌지 확인하면 무조건 시간초과가 나와서,

딕셔너리(해시)를 사용해서 풀었다. 해시는 진짜 진짜 진짜 엄청 빠르다!!

def dfs(depth):
    if depth == M:
        s = ' '.join(map(str, li))
        if s not in d:
            d[s] = 1
            print(s)
        return ;
    for i in range(N):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        check[i] = 0

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
d = {}; li = []
check = [0]*N
dfs(0)

브루트포스 알고리즘 & 백트래킹 문제이다. PyPy3로 제출해야 통과된다.

depth > 1 and li[depth-2] == li[depth-1] == i(현재 선택한 답과 그 전의 2개의 답이 같음) 조건을 성립하지 않는

답을 추가하고, 정답을 10개 다 선택했다면 점수를 확인하고 3 이상이라면 cnt를 올려주면 된다. 

def dfs(depth):
    global cnt
    if depth == 10:
        s = 0
        for j in range(10):
            if li[j] == ans[j]:
                s += 1
        if s >= 5:
            cnt += 1
        return ;
    for i in range(1, 6):
        if depth > 1 and li[depth-2] == li[depth-1] == i:
            continue
        li.append(i)
        dfs(depth+1)
        li.pop()
        
ans = list(map(int, input().split()))
li, cnt = [], 0
dfs(0)
print(cnt)

브루트포스 알고리즘 & 백트래킹 문제이다. 현재 근육량 + 현재 운동 키트 중량 - K가 0 이상일 때만 재귀 함수로

진입하고 depth(운동 일수)가 성공적으로 N이 되었다면 cnt를 올려주면 된다.

def dfs(depth, t):
    global cnt
    if depth == N:
        cnt += 1
        return ;
    for i in range(N):
        if check[i] or t+nums[i]-K < 0:
            continue
        check[i] = 1
        dfs(depth+1, t+nums[i]-K)
        check[i] = 0
        
N, K = map(int, input().split())
nums = list(map(int, input().split()))
check, cnt = [0]*N, 0
dfs(0, 0)
print(cnt)

수학 & 백트래킹 문제이다. 그런데 백트래킹을 써서 푸니까 시간 초과가 나온다.

시간 초과가 뜰 만 한 코드이긴 한데 어떻게 해결해야 할지 모르겠어서 일단 반복문을 사용해서 해결했다.

반복문 풀이(통과)

N = int(input())
s = set()
for i in range(N+1):
    for j in range(N+1 - i):
        for k in range(N+1 - i - j):
            t = N-i-j-k
            n = i + 5*j + 10*k  + 50*t
            s.add(n)

print(len(s))

백트래킹 풀이(시간 초과)

def dfs(depth, s):
    if depth == N:
        check[s] = 1
        return ;
    for i in range(4):
        dfs(depth+1, s+nums[i])
        
N = int(input())
nums = [1, 5, 10, 50]
check = [0]*(50*20+1)
dfs(0, 0)
cnt = 0
for i in check:
    if i:
        cnt += 1
print(cnt)

기본적인 백트래킹 문제이다.

def dfs(depth):
    if depth == M:
        print(*li)
        return ;
    for i in range(N):
        if depth == 0 or li[-1] <= nums[i]:
            li.append(nums[i])
            dfs(depth+1)
            li.pop()
        
N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
li = []
dfs(0)

기본적인 백트래킹 문제이다.

def dfs(depth):
    if depth == M:
        print(*li)
        return ;
    for i in range(N):
        li.append(nums[i])
        dfs(depth+1)
        li.pop()

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
li = []
dfs(0)