개발자취 개발자취

Problem Solving/Baekjoon

• [백준] 10825번 문제 (국영수) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 20. 13:59

  https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net from sys import stdin members = [] for _ in range(int(stdin.readline())): members.append(list(stdin.readline().split())) [print(member[0]) for member in sorted(members, key=lambda m: (-int(m[1]), int(m[2]), -int..

  Read More
• [백준] 2011번 문제 (암호코드) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 20. 13:21

  s = list(input().strip()) length = len(s) dp = [0 for i in range(length + 1)] dp[0], dp[1] = 1, 1 if s[0] == "0": print(0) else: for i in range(2, length + 1): if int(s[i - 1]) > 0: dp[i] += dp[i - 1] num = int(s[i - 1]) + int(s[i - 2]) * 10 if 10

  Read More
• [백준] 2225번 문제 (합분해) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 20. 10:42

  n, k = map(int, input().split()) dp = [[0] * 201 for i in range(201)] for i in range(1, 201): dp[1][i] = 1 for i in range(2, 201): for j in range(1, 201): if j == 1: dp[i][j] = i else: dp[i][j] = dp[i][j - 1] + dp[i - 1][j] print(dp[k][n] % 1000000000) 문제를 풀이한 방법은 매우 단순했다. 1. 숫자를 하나씩 대입해보며 경우의 수를 메모장에 적었다. 2. 경우의 수를 적어가며 규칙을 발견했다. 3. 규칙을 코드로 구현했다. 규칙은 아래 표를 보면 바로 알 수 있다. n = 1 n = 2 n = 3 n = 4 ..

  Read More
• [백준] 9465번 문제 (스티커) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 20. 09:02

  for _ in range(int(input())): t = int(input()) stickers = [[0]] for _ in range(2): stickers.append(list(map(int, input().split()))) if t < 2: print(max(stickers[1][0], stickers[2][0])) else: stickers[1][1] += stickers[2][0] stickers[2][1] += stickers[1][0] for i in range(2, t): stickers[1][i] += max(stickers[2][i - 1], stickers[2][i - 2]) stickers[2][i] += max(stickers[1][i - 1], stickers[1][i -..

  Read More
• [백준] 9095번 문제 (1, 2, 3 더하기) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 20. 09:02

  for _ in range(int(input())): n = int(input()) dp = [0] * 11 dp[1], dp[2], dp[3] = 1, 2, 4 for i in range(4, n + 1): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] print(dp[n]) 해당 숫자 n에 대하여 경우의 수를 나타내면 아래 표와 같다. n n에 대한 경우의 수 1 1 2 2 3 4 4 7 5 13 6 24 7 44 8 81 9 149 표를 보면 dp[i]에 대하여 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 라는 식이 성립한다. 따라서, 최대 입력은 10이기 때문에 10까지 경우의 수를 미리 구해놓고 dp[n]을 출력해줬다.

  Read More
• [백준] 2193번 문제 (이친수) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 20. 09:01

  n = int(input()) dp = [0, 1, 1, 2] for i in range(4, 101): dp.append(dp[i - 1] + dp[i - 2]) print(dp[n]) 자리수 n에 대하여 이친수의 개수를 표로 나타내면 아래와 같다. n n에 대한 이친수의 개수 0 0 1 1 2 1 3 2 4 3 5 5 6 8 표를 보면 숫자 3부터 dp[n] = dp[i - 1] + dp[i - 2] 식이 성립한다는 것을 알 수 있다. 따라서 dp에 0 ~ 3(또는 더 높은 수) 까지 미리 이친수의 개수를 할당해주고 위의 식으로 n까지 for문을 반복하면 이친수의 개수를 알 수 있다.

  Read More
• [백준] 2133번 문제 (타일 채우기) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 19. 16:46

  n = int(input()) dp = [0] * 31 dp[0] = 1 dp[2] = 3 if n % 2 != 0: print(0) else: for i in range(4, n + 1): dp[i] = dp[i - 2] * 3 for j in range(i - 4, -1, -2): dp[i] += dp[j] * 2 print(dp[n]) https://honggom.tistory.com/84 [백준] 11726번 문제 (2 x n 타일링) 파이썬(Python) 풀이 n = int(input()) dp = [0, 1, 2] for i in range(3, 1001): dp.append(dp[i - 2] + dp[i - 1]) print(dp[n] % 10007) 처음에는 도대체 어떻게 풀어야 하나.....

  Read More
• [백준] 1912번 문제 (연속합) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 19. 16:26

  n = int(input()) nums = list(map(int, input().split())) dp = [nums[0]] for i in range(len(nums) - 1): dp.append(max(dp[i] + nums[i + 1], nums[i + 1])) print(max(dp)) 연속된 숫자의 합 중 가장 큰 합을 구하는 문제이다. 풀이는 dp에 max(dp[i] + nums[i + 1], nums[i + 1]) 를 추가해가며 dp 중에 가장 큰 값을 출력하면 된다. 연속된 숫자가 더 크면 dp[i] + nums[i + 1]을 dp에 추가할 것이고, 그렇지 않으면 nums[i + 1]이 추가될 것이다.

  Read More
• [백준] 16194번 문제 (카드 구매하기 2) 파이썬(Python) 풀이

  Problem Solving/Baekjoon 2021. 8. 19. 16:09

  import sys n = int(input()) prices = [0] + list(map(int, input().split())) dp = [0] + [sys.maxsize] * n dp[1] = prices[1] for i in range(2, n + 1): for j in range(1, i + 1): dp[i] = min(dp[i], dp[i - j] + prices[j]) print(dp[n]) https://honggom.tistory.com/79 [백준] 11052번 문제 (카드 구매하기) 파이썬(Python) 풀이 n = int(input()) dp = [0] * (n + 1) prices = [0] + list(map(int, input().split())) dp[1] = prices[..

  Read More
• [백준] 1463번 문제 (1로 만들기) 파이썬(Python) 풀이

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

  n = int(input()) dp = [0] * (n + 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + 1 if i % 3 == 0: dp[i] = min(dp[i], dp[i // 3] + 1) if i % 2 == 0: dp[i] = min(dp[i], dp[i // 2] + 1) print(dp[n]) 처음에는 dp의 개념이 없었기 때문에 풀지 못 한 문제였다. 대부분의 사람이 그리디 문제인 줄 알고 그리디식으로 접근하다가 틀리는 것 같았다. 핵심은 dp에 항상 해당 숫자를 최소한의 연산으로 1로 만든다 가정했을 때, 그 연산이 걸린 횟수를 저장하는 것이다. 숫자 2가 1이 되는데 필요한 최소 연산은 1번이다. 2로 나누거나 1을 빼면 된다. 숫자 3이 1..

  Read More