Patrick's Devlog

1. 개요 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1-1. 설명 2xn 직사각형을 1x2, 2x1과 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 n이 주어지며, n은 1 이상 1,000 이하 2. 구현 2-1. 풀이 Dynamic Programing을 이용하여 풀면 된다. 점화식은 n이 1일때부터 타일을 배치하여 점화식을 찾았다. 점화식은 DP[n] = DP[n-1] + DP[n-2] * 2 임을 알 수 있다. n에..

1. 개요 https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 1-1. 설명 학교 수업을 들은 동준이는 스마트폰 게임을 제작하였다. 총 N개의 레벨이 있으며 각 레벨을 클리어시 점수가 주어진다. 이때, 점수는 레벨에 따라 높아져야 하나, 동준이의 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다. 이를 해결하기 위해 특정 레벨 점수를 감소시키려 한다. 각 레벨을 클리어할때 얻는 점수가 주어졌을때, 몇번 감소시키면 되는지 구하는..

1. 개요 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 1-1. 설명 N x M 크기 배열로 표현되는 미로가 있다. 미로가 이동할 수 있는 칸은 1, 이동할 수 없는 칸은 0으로 나타낸다. 이때 미로가 주어졌을때 (1, 1)에서 출발해 (N, M)의 위치로 이동할때 지나야 하는 최소 칸의 수를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 두 정수 N, M이 주어지며, 각각 2이상 100 이하 - 다음 N개 줄에 M개의 미로 정수가 주어짐 2. 구현 2-1...

1. 개요 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 1-1. 설명 국가는 정해진 예산 내에 최대한의 예산을 지방에 배정해주려고 한다. 각 조건에 맞게 지방에 돈을 분배했을때, 배정된 예산중 최댓값 정수를 출력하는 프로그램을 작성한다. 자세한 조건들과 설명은 위의 링크를 참조한다. 1-2. 제한 사항 - 첫 줄에는 지방 수를 의미하는 N이 주어지며, N은 3 이상 10,000 이하 - 다음 줄에는 각 지방의 예산 요청을 표현하는 N개..

1. 개요 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 1-1. 설명 오늘은 스사트링크에 다니는 사람들이 모여 축구를 한다. 축구를 위해 모인사람은 N명이며, 이는 짝수이다. 이제 N/2명으로 이루어진 스타트팀과 링크팀으로 사람을 나눠야한다. 우리는 능력치를 조사하여 각 팀에 더해지는 능력치가 최소일때를 찾는 프로그램을 구현한다. 문제의 자세한 설명은 위의 링크를 참고한다. 1-2. 제한 사항 - 첫 줄에 N이 주어지며, N은 4 이상 20 이하 짝수 - 둘째 ..

1. 개요 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 1-1. 설명 가로수가 임의의 간격으로 심어져 있다. 우리는 가로수들이 모든 간격이 동일하게 되도록 가로수를 추가로 심게끔 추진한다. 최대한 적은 가로수의 수로 같은 간격이 되도록 할때, 심어야 할 최소의 가로수 수를 구하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에는 이미 심어져있는 가로수의 수를 나타내는 정수 N이며, 3이상 100,000 이하 정수 - 둘째 줄부터..

1. 개요 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1-1. 설명 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇개의 수를 선택해 구할 수 있는 합 중 가장 큰 합을 구하려 한다. 단, 수는 한 개이상 선택해야 한다. 1-2. 제한 사항 - 첫 줄에 정수 n이 주어지며, n은 1 이상 100,000 이하 - 둘째 줄에는 n개의 정수로 이루어진 수열이 주어지며, 수는 -1,000 이상 1,000 이하 2. 구현 2-1. 풀이..

1. 개요 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 1-1. 설명 아래 그림과 같이 정사각형 모양 지도가 있다. 집이 있는곳은 1, 없는 곳은 0으로 나타낸다. 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지 번호를 붙이려 한다. 아래 오른쪽 그림은 단지별로 번호를 붙인 것이다. 지도를 입력해 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성한다. 1-2. 제한 사항 - 첫 줄에 지..