Patrick's Devlog

1. 개요 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1-1. 설명 N번째 피보나치를 구하게 된다면 재귀를 통해 0부터 N의 피보나치 값들이 구해지게 될 것이다. 여기서 fibonacci(N) 함수를 호출했을 때, 0과 1이 각각 몇번 출력되는지 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 테스트 케이스 개수 T가 주어짐 - 각 테스트 케이스는 한줄로 이루어져 있으며, N이 주어짐 - N은 40 이하 자연수 or 0 2. 구현 2-1. 풀이 DP의 bottom-up 방식을 이용해 풀어야겠다고 생각했다. 간략하게 표를 살..

1. 개요 https://www.acmicpc.net/problem/10431 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 1-1. 설명 초등학교 선생님은 아이들을 데리고 단체로 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키순서대로 번호를 부여한다. 번호 부여시 키가 가장 작은 아이가 1번, 그다음 2번, ... 가장 큰 아이는 20번이 된다. 반 아이들은 항상 20명이며 다행히 같은 키를 가진 학생은 한명도 없으므로 아이들은 번호를 인지하고 한줄로 세우면 제대로 된 위치에 잘 서게 된다. 하지만..

1. 개요 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1-1. 설명 절댓값 힙은 아래와 같은 연산을 지원하는 자료구조이다. - 배열에 정수 x를 넣음 - 배열에서 절댓값이 가장 작은 값을 출력후 그 값을 배열에서 제거 - 절댓값이 가장작은 값이 여러개일 경우, 가장 작은 수를 출력하고 그 값을 배열에서 제거 절댓값 힙이 동작하는 프로그램을 작성하라. 1-2. 제한 사항 - 첫 줄에 연산 개수 N이 주어지며 N은 1 이..

1. 개요 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1-1. 설명 캠프에서 쓸 N개의 랜선을 만들어야 한다. 이미 자체적으로 K개의 랜선을 지니고 있으나, K개의 랜선 길이는 제각각이다. N개의 같은 길이 랜선을 만들기 위해 K개의 랜선을 잘라 만들어야 한다. 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이가 없다고 가정하고, 기존 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리..

1. 개요 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 1-1. 설명 N개 로프가 있다. 이 로프를 이용해 물체를 들어올릴 수 잇다. 각각의 로프는 굵기나 길이가 다르므로 물체의 중량이 서로 다를 수 있다. 하지만 여러개 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개 로프를 이용해 중량이 w인 물체를 들어올릴 때, 각각 로프에는 모두 고르게 w/k만큼 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을..

1. 개요 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 1-1. 설명 눈금 간격이 1인 MxN 크기 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇개의 분리된 영역으로 나누어진다. 위의 처럼 영역의 넓이가 3개로 나눠지는 것을 확인할 수 있다. M,N과 K 그리고 K개의 직사각형 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 ..

1. 개요 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1-1. 설명 n가지 종류 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해 그 가치의 합이 k원이 되도록 한다. 그 경우의 수를 구하는 프로그램을 작성한다. 각각의 동전은 몇 개라도 사용 가능하다. 1-2. 제한 사항 - 첫 줄에 n과 k가 주어지며 n은 1 이상 100 이하, k는 1 이상 10,000 이하 - 다음 n개 줄에는 각각의 동전 가치가 주어지며..

1. 개요 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1-1. 설명 효주는 포도주 시식회에 갔다. 그 곳에서, 테이블 위 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 포도주를 시식하려는데 두가지 규칙이 존재한다. - 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야하며, 마신 후에는 원래 위치에 다시 놓아야 함 - 연속으로 놓여있는 3잔 모두 마실 수 X 효주는 되는대로 많은 양의 포도주를 맛보기 위해 어떤 포도주 ..