코딩하는 해맑은 거북이

해당 글은 백준 1699번 문제 '제곱수의 합'을 다룬다. 문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 설명 해당 문제는 DP로 해결할 수 있고, 점화식을 아래와 같이 표현된다. 현재 숫자 i에서 1~(i-1)까지 값을 j라고 했을 때, 해당 값의 제곱한 결과를 뺀 dp값 + 1이 작다면 dp값을 업데이트 해준다. if dp[i] > dp[i-j**2]+1: dp[i] = dp[i-j**2]+1 ..

해당 글은 백준 5639번 문제 '이진 검색 트리'을 다룬다. 문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 설명 전위순회 결과를 확인하면서, left를 root, right까지의 값을 확인하며 큰 값이 있다면 해당 값을 기준으로 2부분으로 쪼개서 재귀를 돌린다. 해당 과정을 left > right가 될 때까지 반복한다. 코드 import sys input = sys.stdin.readline sys.setrecursionl..

해당 글은 백준 2565번 문제 '전깃줄'을 다룬다. 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 설명 처음에는 해당 문제를 BFS로 모든 경우의 수를 구했었는데 시간초과가 떴다. 찾아본 결과 LIS(Longest Increasing Subsequence)와 DP를 합쳐서 해결하면 풀 수 있다고 한다..! * 참고한 풀이영상 : https://www.youtube.com/watch?v=wn2dyWt9ml0 코드 import sys input ..

해당 글은 백준 2630번 문제 '색종이 만들기'을 다룬다. 문제 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 설명 해당 문제는 쪼개진 사각형안에 포함된 color가 다른 게 있다면, 재귀 함수를 통해서 N//2 씩 계속해서 나누어서 해결할 수 있다. 주의할 점은 재귀함수 4번 호출하는 구간에서 마지막에 return을 해주어서 재귀함수를 종료하게 해주어야 한다. 코드 n = int(input()) arr = [] ..

해당 글은 백준 2293번 문제 '동전 1'을 다룬다. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 설명 해당 문제는 DP를 사용해서, 1부터 K원까지 돌며 각 동전으로 만들 수 있는 경우의 수를 더해주면 해결할 수 있다. 알고리즘 분류는 어떤건지 쉽게 떠오르는데, 그 알고리즘을 빠르게 구현하는게 어려운 것 같다.. 코드 n, k = map(int, input().split()) coin = [] for _ in range(n): coi..

해당 글은 백준 15686번 문제 '치킨 배달'을 다룬다. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 설명 조합 라이브러리와 3중 for문으로 해결할 수 있는 문제..! 문제만 읽었을 땐, 쉬워보였는데 의외로 오래 걸렸당.. 치킨집이 아니라 집을 기준으로 조합으로 얻은 m개의 치킨집의 거리를 구해야 하는데 핵심이다! 코드 from itertools import combinations n, m = map(int, ..