wgrgwg-dev

4811 : 알약https://www.acmicpc.net/problem/4811 문제70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이..

2623 : 음악프로그램https://www.acmicpc.net/problem/2623 문제인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다.그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD들이 가져온 것은 아래와 같다.1 4 36 2 5 42 3첫 번째 보조 PD는 1번 가수가 먼저, 다음에 4번 가수, 다음에 3번 가수가 출연하기로 순서를 정했다. 두 번째 보조 PD는 6번, 2번, 5번, 4번 순으로 자기 담당 가수들의 순서를 ..

1806 : 부분합https://www.acmicpc.net/problem/1806 문제10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N (10 ≤ N 출력첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.누적합과 투포인터를 사용해서 풀이하였다. start ~ end 구간의 합을 구할 때는 누적합을 사용하였고, 구간의 합이 S 보다 크면 start를 이동시키고, 작으면 end를 이동시켜서 구간을 조정해 주었다. 코드는 다음과 같다. package gold;import java.util..

14003 :가장 긴 증가하는 부분 수열 5https://www.acmicpc.net/problem/14003 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다...

1027 : 고층 건물https://www.acmicpc.net/problem/1027 문제세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.입력첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그..

1005 : ACM Crafthttps://www.acmicpc.net/problem/1005 문제서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자.이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2..

9663 : N-Queenhttps://www.acmicpc.net/problem/9663 문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (1 ≤ N 출력첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.처음엔 dp 문제인 줄 알았는데, 백트래킹으로 풀 수 있었다. 간단하게 백트래킹 방식을 사용해서 위치를 하나씩 골라가며 퀸을 놓고, 퀸을 n번 놓았을 경우 경우의 수를 카운팅해준다.여기서 일반적인 위치 선택, 즉 NxN으로 무작위로 선택하면 시간초과가 발생한다.따라서 아이디어가 필요한데, 퀸은 한 행에 하나만 놓을 수 있으므로 ..

2133 : 타일 채우기https://www.acmicpc.net/problem/2133 문제3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.입력첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.출력첫째 줄에 경우의 수를 출력한다.규칙만 찾는다면 쉽게 풀 수 있는데, 일단 3x2를 채우는 경우의 수는 3가지다. 3x4 부터 3x(2n) 개를 채우는 특수 패턴 경우의 수는 무조건 2개씩 존재한다. 따라서 dp 풀이 과정을 다음과 같이 세우면 된다. 문제정의 : dp[n] = 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수초기조건 : dp[0] = 1로 가정, 3×2 벽을 채우는 경우의 수 3가지dp[0] = 1;dp[2] = 3;점화식마지막이 2칸짜리 특수패턴..