Problem Solving
-
[백준] 2011번 문제 (암호코드) 파이썬(Python) 풀이Problem Solving 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, 1if 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 한 20분 정도 규칙을 찾으려고 노력했으나, 솔루션이 떠오르지 않아 다른 사람의 풀이를 보았다.풀이를 보니 생각보다 복잡하지는 않았다. 입력으로 주어진 숫자들을 하나부터 끝까지 훑어보며 dp에 경우의 수를 추가..
-
[백준] 1463번 문제 (1로 만들기) 파이썬(Python) 풀이Problem Solving 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로 나누거나 ..
-
[백준] 1929번 문제 (에라토스테네스의 체, 소수 구하기) 파이썬(Python) 풀이Problem Solving 2021. 5. 24. 11:14
def is_prime(num): if num == 1: return False else: for i in range(2, int(num ** 0.5)+1): if num % i == 0: return False return Truem, n = map(int, input().split())for i in range(m, n+1): if is_prime(i): print(i)내가 작성한 코드 우선 처음 접근은 주어진 숫자 n에 대하여 2부터 n-1까지 나눠보면서 나눠지면 소수가 아니게 되므로 그 외의 수를 구하는 방식으로 접근했다. 하면서 예상은 했지만 이런 식으로 접근하게 되면 n이 1,000..