백준 문제 풀이 - 포도주 시식 (2156 문제) 문제 문제 확인하기 풀이 조건부터 확인해보자. 포도주 n잔이 주어진다고 했다. 입력받은 n잔의 포도주를 담은 배열을 wines라는 배열로 초기화하겠다. 첫번째 잔을 1로 표시하기 위해 wines[n+1]로 선언하고 인덱스 1부터 n까지 초기화 하자. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] wines = new int[n + 1]; for (int i = 1; i

백준 문제 풀이 - 가장 긴 증가하는 부분 수열 (11053 문제) 문제 문제 확인하기 풀이 증가하는 부분 수열이란 배열 arr이 주어졌을 때, 특정 몇몇 원소를 제외한 수열이 계속해서 이전 원소보다 큰 형태의 수열을 말한다. 예를 들어 { 1, 3, 7, 4, 2, 5, 6 } 이라는 배열이 있다고 하자. 이 배열에 대한 증가하는 부분 수열은 { 1, 3, 7 } { 1, 3, 4, 5, 6 } { 1, 2, 5, 6 } 와 같은 수열이 될 수 있다. 가장 긴 증가하는 부분 수열이란, 위 증가하는 부분 수열들 중에서 가장 긴 길이의 수열을 말한다. 여기서는 { 1, 3, 4, 5, 6 } 수열이 길이 5로 가장 길기 때문에, 해당 수열이 가장 긴 길이의 수열이 된다. 어떻게 이를 구할 수 있을까? 내가..

백준 문제 풀이 - 쉬운 계단 수 (10844번 문제) 백준 10844번 : 쉬운 계단 수 본문 제한 시간 제한 메모리 제한 1초 256MB 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 1 예제 출력 1 9 예제 입력 2 2 예제 출력 2 17 풀이 어떻게 문제를 풀 수 있을지 '계단 수'를 직접 작성해보면서 규칙을 확인해보자. 먼저 N이..

피보나치 함수 (BOJ : 1003) 백준 1003번 : 피보나치 함수 본문 제한 시간 제한 메모리 제한 0.25초 128MB 문제 다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다. int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } fibonacci(3)을 호출하면 다음과 같은 일이 일어난다. fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다. fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fib..

프로그래머스 : 부대복귀 (Java) 문제 링크 확인 풀이 최단 거리를 구하는 문제이다. 문제가 어려운 것 같지만 차근차근 읽어보면 생각보다 쉽게 문제를 풀 수 있다. 문제에서 주어진 조건을 정리하자면 다음과 같다. n은 총 지역의 수를 의미한다. roads는 roads[x][2]의 크기로 roads[x][0]과 roads[x][1]은 서로 이어진 경로가 있다는 것을 의미한다. road[x][0]에서 road[x][1]로 경로가 있다는 것은, road[x][1]에서 road[x][0]으로도 이동할 수 있다는 의미이다. 각 지역의 이동 비용은 1이다. sources는 1차원 배열로 부대원들이 각각 출발하는 지역을 의미한다. destination은 부대원들이 도착해야 할 목적지를 말한다. 여기서 중요한 점은..

프로그래머스 : 디펜스 게임 (Java) 문제 링크 확인 풀이 처음 가지고 있는 병사 수 n, 무적권의 수 k, 라운드마다 등장하는 적의 수를 담은 1차원 배열 enemy가 주어진다. i번째 라운드의 적의 수 enemy[i]를 막으려면 n개의 가지고 있는 병사(목숨)에서 enemy[i] 만큼을 차감하고, 차감한 후의 n값이 0 이상이어야 해당 라운드를 통과한 것으로 본다. 간단하게 로직을 구상해보자. 남은 병사 수 remain을 선언한다. 초기값은 n 값과 같다. 최대 enemy 배열 길이만큼 아래 내용을 반복한다. (현재 i번째 반복) remain에서 enemy[i]를 빼준다. 조건을 만족하는 한가지를 진행한다. 만약 enemy[i]를 뺀 remain이 0보다 작다면 라운드를 통과할 수 없다. rema..

프로그래머스 : 점 찍기 (Java) 문제 링크 확인 풀이 입력되는 정수 k, d에 대하여 조건을 만족하는 (x, y) 좌표를 찾아야 한다. 문제에서 조건은 다음과 같다. 원점(0, 0)과의 거리가 d를 넘지 않아야 한다. 좌표의 x, y 값은 k의 배수이다. 기본적으로 원점과 x=0 일 때 y 좌표값, y=0 일 때 x 좌표값들의 개수를 추가해둔다. 코드로 나타내면 아래와 같다. long answer = 1; // 원점 1개 // d : 최대 거리 // d를 k로 나눈 값에 2를 곱해주면, // x=0 일 때, y=0 일 때의 좌표값들의 개수이다. answer += ((d / k) * 2); 이제 x, y가 0이 아닐 때 좌표 조합을 구해야 한다. (x, y) 좌표와 원점과의 거리가 d를 넘지 않아야 ..

예산(BOJ : 2512) 백준 2512번 : 예산 본문 제한 시간 제한 메모리 제한 1초 128MB 문제 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 1..

랜선 자르기(BOJ : 1654) 백준 1654번 : 랜선 자르기 본문 제한 시간 제한 메모리 제한 2초 128MB 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선..

나무 자르기(BOJ : 2805) 백준 2805번 : 나무 자르기 본문 제한 시간 제한 메모리 제한 1초 256MB 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높..