https://www.acmicpc.net/problem/1188 접근 방법 - 수학적 접근이 필요하여 문제 난이도에 비하여 정답률이 높은 문제이다. - 문제의 중요 힌트는 '모두가 동일한 양의 소시지'를 받아야 한다는 점이다. - 우선, 주어지는 소시지의 수(N)이 평론가의 수(M)보다 많다면, 자르지 않은 소시지를 동일하게 나눠주고 남은 소시지를 잘라서 배분하면 된다. - 즉, 소시지의 수와 평론가의 수가 1 외의 수로 나눠지지 않는다면, N/M 크기의 소시지로 무조건 나눠줄 수 있다는 것이 핵심이다. - 위 핵심을 이용하기 위하여 최대 공약수를 활용하여 문제를 풀어주었다. 해결 방법1. N/M 크기로 소시지를 나눠주는 것이 목적이다. 이를 위해서 소시지의 수가 평론가의 수보다 많은 경우, N을 ..

백준 30805 - 사전 순 최대 공통 부분 수열 시간제한 1초, 메모리 제한 1024MB출력A와 B의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 크기 K를 출력하시오.K != 0이라면, 다음 줄에 K개의 수를 공백으로 구분해 출력하세요.i번째 수는 A와 B의 공통 부분 수열 중 사전 순으로 가장 나중인 수열의 i번째 수입니다.접근 방법마땅한 풀이 방법이 안 떠올라 생각을 조금 많이 했다.핵심은, 서로 다른 두 수열의 공통된 부분 수열이어야 한다는 점, 사전 순으로 가장 나중인 수열을 구해야 한다는 점이다.따라서, 아래와 같이 풀이하였다.입력받는 두 수열의 각 수들의 인덱스를 기록해놓는다. => 1 1 3 5 라면 [0, 1], [], [2], [], [3]수의 최댓값이 100이므로, 100부..

https://www.acmicpc.net/problem/18513 접근 방법1. 문제에서 샘터의 범위가 -1억 ~ 1억까지이다. 큰 범위이므로, 위치의 크기만큼 리스트를 생성하면 메모리 또는 시간 초과가 날 것이다.2. 따라서, visited 배열이 아닌 set을 활용하여 방문한 곳을 기록해준다.3. 각 쉼터에서 1칸씩, 2칸씩 갈 수 있는 곳을 점차 넓혀 나가는 것이 최소의 값을 구하는 방법이므로 bfs를 이용하여 풀어준다.4. q에는 (시작위치, 현재 위치)를 담아주고, 각 쉼터에서 -1, +1을 한 곳을 방문하지 않았다면 q에 담아준 후 result에 거리 차이만큼 +, 남은 집의 갯수를 -1 해주면 된다. import syssys.stdin = open('input.txt')input = sys..

https://www.acmicpc.net/problem/19947 접근 방법1. n년 후의 최적의 값을 도출하여야 한다. 2. 받을 수 있는 이자의 방식이 3가지이므로 1년, 3년, 5년 전의 값에서 투자 방식에 따라 최대 값으로 갱신해주면 된다. import syssys.stdin = open('input.txt')input = sys.stdin.readlineH, Y = map(int, input().split())results = [0] * (Y+1)results[0] = Hfor i in range(1, Y+1): for j in [1, 3, 5]: if i - j

백준 14925 - 목장 건설하기시간 제한 1초, 메모리 제한 512MB# 조건랜드 씨는 퇴직금으로 땅을 사서 목장을 지으려 한다. 그가 사려고 소개받은 땅은 직사각형이고 대부분 들판이지만, 여기저기에 베기 어려운 나무와 치울 수 없는 바위가 있다.그는 목장을 하나의 정사각형으로 최대한 크게 지으려 하는데, 그 안에 나무나 바위는 없어야 한다. 땅의 세로 길이가 M미터, 가로 길이가 N미터일 때, 1미터 간격의 격자로 된 땅의 지도를 M x N행렬로 표현하자. 이때, 행렬의 원소 0은 들판, 1은 나무 그리고 2는 돌을 의미한다. 랜드씨의 땅에서 지을 수 있는 가장 큰 정사각형 목장의 한 변의 크기 L을 출력하시오.# 접근 방법DP를 이용하여 풀어준다.records 테이블은 M행 N열을 오른쪽 아래 ..

백준 18427 - 함께 블록 쌓기시간 제한 1초, 메모리 제한 256MB# 조건1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다.단, 어떤 학생의 블록은 사용하지 않아도 되며 한 학생당 최대 1개의 블록만을 사용할 수 있다.1번부터 N번까지의 학생들이 가지고 있는 블록들에 대한 정보가 주어졌을 때, 높이가 정확히 H인 탑을 만들 수 있는 경우의 수를 계산하는 프로그램을 작성하시오.예를 들어 N=3, M=3, H=5일 때, 각 학생마다 가지고 있는 블록들의 높이가 다음..

백준 1535 - 안녕시간 제한 2초, 메모리 제한 128MB# 조건세준이는 성형수술을 한 후에 병원에 너무 오래 입원해 있었다. 이제 세준이가 병원에 입원한 동안 자기를 생각해준 사람들에게 감사하다고 말할 차례이다.세준이를 생각해준 사람은 총 N명이 있다. 사람의 번호는 1번부터 N번까지 있다. 세준이가 i번 사람에게 인사를 하면 L[i]만큼의 체력을 잃고, J[i]만큼의 기쁨을 얻는다. 세준이는 각각의 사람에게 최대 1번만 말할 수 있다.세준이의 목표는 주어진 체력내에서 최대한의 기쁨을 느끼는 것이다. 세준이의 체력은 100이고, 기쁨은 0이다. 만약 세준이의 체력이 0이나 음수가 되면, 죽어서 아무런 기쁨을 못 느낀 것이 된다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 프로그램을 작성하시오.입력..

백준 15681 - 트리와 쿼리시간 제한 1초, 메모리 제한 128MB# 조건간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.입력트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.출력Q줄에 걸쳐 각 쿼리의..

백준 5972 - 택배 배송시간 제한 1초, 메모리 제한 128MB# 조건농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.농부 현서에게는 지도가 있습니다. N (1 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 다음 지도를 참고하세요. [2]--- / | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]---..