https://www.acmicpc.net/problem/174000001 -> 1 00010 -> 3 00011 ->1+3 = 4한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수 -> 이진수처럼 계산하되, 제곱되는 수를 3으로 하면 됨 ( 각 자리당 0,1만 가능 - 같은 수 두 번 이상 더할 수 없기 때문!!) 따라서 n을 이진수로 변환한 뒤에, 각 자릿수를 더할 때 2의 제곱들을 더하는 게 아니라 3의 제곱을 각 자릿수만큼 계산해서 더하면 된다.import sysinput = sys.stdin.readlinen = int(input())ans=0idx=1while n>1: ans+=(n%2)*idx n//=2 idx*=3ans+=n*idxprint(ans)
https://www.acmicpc.net/problem/1932선택된 수의 합이 최대가 되는 경로를 구하기 위해 DP를 사용한다.아래층에 있는 수는 현재 층에서 선택된 대각선의 왼쪽 혹은 오른쪽에 있는 것만 가능 -> 배열 상 위에가 k번째일때, 아래에서는 k나 k+1만 선택가능하다.위에서 아래로 내려가며 고려하는 것보다, 아래에서 위로 올라가며 최종 선택되어 도출된 하나의 값이 자연스레 최대의 값이 되도록 하는 것이 편하다!!따라서 위(k번째 값)에서는 아래 k, k+1중 큰 값을 현재에 더한다. 이를 해당 레벨의 반복을 돌린 후, 더 위의 레벨로 올라가 다시 아래에서 이동 가능한 두 값중 더 큰값을 현재 위치의 값에 더한다.이를 반복한다면, 가장 상위에 있는 하나의 값은 자연적으로 갈 수 있는 모든..
https://www.acmicpc.net/problem/17626python3으로 내니까 안 돼서 찾아보니까 pypy3으로 내면 된다길래 내보니까 진짜됨...허무import sysimport mathinput = sys.stdin.readlinen = int(input())dp = [i for i in range(n+1)]for i in range(2, n+1): sqrt = int(math.sqrt(i)) for x in range(sqrt, 0, -1): if dp[i] > dp[i-x*x]+1 : dp[i] = dp[i-x*x]+1print(dp[n])
https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr처음 DFS + 백트래킹으로 푼 답안 (맞음)- 최소 횟수를 구하는 것이므로 BFS가 논리적으로 더 좋은 건 알지만 구현 방법이 아리송해서 DFS로 우선 풀었다!!answer = 51def solution(begin, target, words): global answer visited = [False for _ in range(len(words))] for i in range(len(words)): if onecha..
https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr정렬하는 방법 익히기 - 한 줄로 작성하는 for 문, 람다 등 사용!!!def solution(sizes): sizes = [sorted(size, reverse=True) for size in sizes] return max(x for x, _ in sizes)*max(y for _, y in sizes) https://school.programmers.co.kr/learn/courses/30/less..
https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr배열 안에 있는 각 숫자는 1000 이하이기 때문에 글자 수 맞춰서 정렬해줌만약에 "30" vs "3"이렇게 비교하면 원래 문자열이었으면 30이 더 큰 걸로 여겨져서 30이 먼저나옴(내림차순 정렬 시)근데 사실 그러면 안 되고, 3이 먼저 나와야 함-> 해당 숫자를 3번 반복해서 붙였을 때 "333"과 "303030"이 비교되게 끔 함def solution(numbers): numtostr = list(map(str, numbers)) ..
https://www.acmicpc.net/problem/2294당연히 dp로 풀어야된다import sysinput = sys.stdin.readlinen, k = map(int, input().split())coins = [0 for _ in range(n)]for i in range(len(coins)): coins[i] = int(input())coins.sort()dp = [0 for _ in range(k+1)]for i in range(1, k+1): for coin in coins: if coin>i: break if i-coin!=0 and dp[i-coin]==0: continue dp[i] = dp[i-coin]+1 if dp[i]==0 ..
https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr# 최단거리 -> BFS 사용from collections import dequedef solution(maps): queue = deque() n = len(maps) m = len(maps[0]) # 방향 이동 mv = [[1,0],[0,1],[-1,0],[0,-1]] queue.append((0,0)) # 시작점 while queue: x,y = queue.popleft() ..
https://www.acmicpc.net/problem/2096DP 문제지만 메모리 제한이 빡센 편이라 최소의 공간을 사용하게 배열을 설계해야 한다!이번 문제에서는 DP 배열에서 딱 직전의 값과, 입력 들어오는 숫자 값만 고려하면 되기 때문에 한 행짜리 배열로 DP를 풀었다.import sysinput = sys.stdin.readlinen = int(input()) # linesnums = list(map(int, input().split()))prev_min = nums[:]prev_max = nums[:]for i in range(1,n): nums = list(map(int, input().split())) # min curr_min = [ min(prev_min[0..
https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krdef solution(nums): # 최대 종류 -> n/2 개 return min(len(nums)/2, len(set(nums)))https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr def solution(phone_boo..
