기록방

👉 문제링크 1251번: 단어 나누기 알파벳 소문자로 이루어진 단어를 가지고 아래와 같은 과정을 해 보려고 한다. 먼저 단어에서 임의의 두 부분을 골라서 단어를 쪼갠다. 즉, 주어진 단어를 세 개의 더 작은 단어로 나누는 것이다 www.acmicpc.net 🔸 문제 분석 🔸 문자를 3개로 나눠서 뒤집고 합쳤을때 사전순으로 가장 앞에 오는 경우를 찾는다. 브루트포스 알고리즘이다. 🔸 코드 🔸 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); int len = s.length(); String ans..

👉 문제링크 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net 🔸 문제 분석 🔸 입력받은 리스트의 원소로 만들 수 있는 삼각 수열의 최대 길이를 출력한다. 그리디적인 관점과 브루트포스의 접근이 모두 필요하다. 입력받은 리스트를 오름차순 정렬했을때, arr[i] + arr[i+1] > arr[n] 을 만족하면 i부터 n 사이의 모든 수들도 삼각관계이다. (그리디) 가장 앞이나 가장 뒤를 빼가며 가장 긴 부분 삼각 수열을 찾는다. (브루트포스..

👉 문제링크 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 🔸 문제 분석 🔸 재료 선택에 따라 신맛과 쓴맛의 합이 변한다. 신맛(s)은 곱으로 계산한다. 쓴맛(b)은 합으로 계산한다. 신맛과 쓴맛의 차이의 최소값을 출력한다. 🔸 코드 🔸 n = int(input()) taste = [] visit = [0] * n answer = 1000000000 for _ in range(n): taste.append(list(map(int,input().split()))) def dfs(d, m,..

👉 문제링크 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 🔸 문제 분석 🔸 최소비용으로 세 꽃을 심을 수 있는 최소 비용을 출력한다. 모든 경우의 수를 탐색해야하는 브루트 포스 문제이다. 🔸 코드 🔸 import sys input = sys.stdin.readline N = int(input()) flower = [] visit = [[0]*N for _ in range(N)] answer = 200*16 dx = [0, 0, -1, 0, 1] dy = [0, -1, 0, 1, 0] for i in ran..

👉 문제링크 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 🔸 문제 분석 🔸 입력받은 n을 제곱수의 합으로 표현할 때 최소한의 경우의 수를 출력한다. dp 와 브루트 포스 풀이 두 가지가 가능하다. dp dp[n] 리스트는 n을 만드는데 들어가는 '제곱수 합 경우의 수의 최소값'을 저장한다. dp[0] = 0, dp[1] = 1 로 초기화한다. dp[n]을 구할 때, 1부터 j의 제곱수(j**2)가 i보다 커질때까지 반복하며 최소값을 찾는다. min_v : i에서 j**2를..