개발자취 개발자취

Problem Solving/Baekjoon

• [백준] 9461번 문제 (파도반 수열) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 19. 11:18

  for _ in range(int(input())): n = int(input()) dp = [0] * 101 dp[1], dp[2], dp[3] = 1, 1, 1 dp[4], dp[5] = 2, 2 for i in range(6, n + 1): dp[i] = dp[i - 1] + dp[i - 5] print(dp[n]) 가장 긴 변의 길이를 하나 씩 적어보면 5번째 긴 변부터 일정한 규칙으로 수열이 형성되는 것을 알 수 있다. 규칙은 바로 dp[index] = dp[index - 1] + dp[index - 5] 이며, 해당 식을 적용하면 정답을 구할 수 있다.

  Read More
• [백준] 2156번 문제 (포도주 시식) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 15. 19:24

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 t = int(input()) wines = [0] + [int(input()) for _ in range(t)] dp = [0] + [wines[1]] if t > 1: dp.append(wines[1] + wines[2]) for i in range(3, t + 1): case1 = dp[i - 1] # 이번 포도주를 안 먹는 경우 case2 = wines[i] + dp[i - 2] # 이번 포도주를 먹고 저번 포도주를 안 먹는 경우 case3 = wines[i] + wines[i - 1] + dp[i - 3] # 이번 포도주를 먹고 저번 포도주를 먹는 경우 dp.append(max(case1, case2, case3)) print(dp[t]..

  Read More
• [백준] 1699번 문제 (제곱수의 합) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 14. 18:20

  import sys n = int(input()) dp = [0] * 100001 dp[1], dp[2], dp[3], dp[4] = 1, 2, 3, 1 for i in range(5, n + 1): if int(i ** 0.5) ** 2 == i: dp[i] = 1 else: if dp[i - 1] + dp[1] == 2: dp[i] = 2 else: left, right = 1, i - 1 count = sys.maxsize while left < right: count = min(count, dp[left] + dp[right]) left += 1 right -= 1 dp[i] = count print(dp[n]) 나의 풀이는 이렇다. 사실 Python3 컴파일러로는 시간초과가 나길래 PyPy3로 ..

  Read More
• [백준] 17103번 문제 (골드바흐 파티션) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 11. 11:00

  def is_prime(num): if num == 1 or num == 0: return False else: for i in range(2, int(num ** 0.5)+1): if num % i == 0: return False return True primes = [is_prime(i) for i in range(1000001)] t = int(input()) for _ in range(t): n = int(input()) left, right = 0, n count = 0 while left n: right -= 1 else: left += 1 print(count) 우선 최대 입력인 1,000,000 까지 for문을 돌면서 소수면 True 아니면 False의 형태로 primes 리스트에 할당 ..

  Read More
• [백준] 17299번 문제 (오등큰수) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 6. 14:10

  from collections import Counter from sys import stdin n = int(stdin.readline()) nums = list(map(int, stdin.readline().split())) nums_count = Counter(nums) result = [-1] * n stack = [0] for i in range(1, n): while stack and nums_count[nums[stack[-1]]] < nums_count[nums[i]]: result[stack.pop()] = nums[i] stack.append(i) print(*result) 우선 이 문제를 풀기 전에 아래 링크에 오큰수 문제를 풀어보면 좋다. (문제가 매우 유사함) https://www..

  Read More
• [백준] 1003번 문제 (나이순 정렬) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 7. 6. 17:36

  t = int(input()) members = [] for i in range(t): tmp = input().split() tmp.append(i) members.append(tmp) members.sort(key=lambda x: (int(x[0]), x[2])) for member in members: print(member[0], member[1]) 단순히 정렬하는 문제지만 만약 나이가 같으면 가입 순으로 정렬해야 한다. 가입 순으로 정렬하기 위해서 members에 가입자들을 삽입할 때 (for문) index를 같이 넣어줬고, 람다식에서 x[0](나이)순으로 정렬하고 만약 같으면 가입순 x[2](가입)순으로 정렬했다.

  Read More
• [백준] 1003번 문제 (피보나치 함수) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 7. 6. 16:36

  첫 번째 풀이 (시간 초과) def zero_func(): global zero zero += 1 return zero def one_func(): global one one += 1 return one def fibo(num): if num == 0: return zero_func() elif num == 1: return one_func() else: return fibo(num - 1) + fibo(num - 2) from sys import stdin t = int(stdin.readline()) for _ in range(t): zero = 0 one = 0 fibo(int(stdin.readline())) print(zero, one) 아주 쉽게 접근해서 숫자가 0인 경우와 1인 경우에 함수를..

  Read More
• [백준] 10828번 문제 (스택) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 6. 8. 22:02

  import sys stack = [] for _ in range(int(sys.stdin.readline())): cmd = sys.stdin.readline().split() if len(cmd) == 2: stack.append(cmd[1]) elif cmd[0] == 'top': if len(stack) == 0: print(-1) else: print(stack[-1]) elif cmd[0] == 'size': print(len(stack)) elif cmd[0] == 'empty': print(1 if len(stack) == 0 else 0) elif cmd[0] == 'pop': if len(stack) == 0: print(-1) else: data = stack[-1] del stack..

  Read More
• [백준] 1002번 문제 (터렛) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 5. 25. 16:46

  # 터렛 n = int(input()) for _ in range(n): x1, y1, r1, x2, y2, r2 = map(int, input().split()) r = ((x2-x1)**2+(y2-y1)**2)**0.5 R = [r1, r2, r] maxR = max(R) R.remove(maxR) if r == 0 and r1 == r2: print(-1) elif r == r1+r2 or maxR == sum(R): print(1) elif maxR > sum(R): print(0) else: print(2) 일단 끝내 풀지 못했다.. 정답에 거의 근접했던 것 같으나 조건을 몇 개 빼먹어서 맞추지 못하고 다른 사람이 작성한 코드중에 제일 기가 막히게 작성한 코드라고 생각된 코드를 들고왔다. 출처 ..

  Read More
• [백준] 9020번 문제 (골드바흐의 추측) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 5. 24. 17:01

  # 골드바흐의 추측 import sys def getPrime(num): primeList = [] for i in range(2, num): isPrime = True for j in range(2, int(i**0.5)+1): if i % j == 0: isPrime = False break if isPrime: primeList.append(i) return primeList for _ in range(int(sys.stdin.readline())): n = int(sys.stdin.readline()) primeList = getPrime(n) check = [] if int(n / 2) in primeList: print("%d %d" % (n/2, n/2)) else: for a in prim..

  Read More