하늘을 날고 싶은 펭귄

[백준, BOJ] 1920 - 수 찾기 (C++)

안녕하세요! 오늘은 BOJ 1920 - 수 찾기 문제를 풀어볼게요. 1. 접근 - 선형 탐색문제를 읽어보면, N개의 정수 배열 A[N]이 주어지고 나서, M개의 수가 A 배열 안에 있는지 찾아야 해요.이때 숫자를 배열에서 앞에서부터 하나씩 찾는다고 생각해볼게요. 문제의 예시 입력대로, N = 5, A[5] = {4, 1, 5, 2, 3}이고, M = 5, 즉, 5개의 숫자 1, 3, 7, 9, 5를 차례로 A 배열에서 찾을 거예요.앞에서부터 순차적으로 찾는다고 생각해 보면, 배열의 앞쪽에 위치한 1을 찾을 때에는 A[1]에 값이 있으니 금방 찾을 수 있지만, 배열의 끝에 있는 4를 찾을 때에는 A[4]에 값이 있으니 배열의 끝까지 탐색해보아야 해요.존재하지 않는 수를 찾을 때에도 배열을 처음부터 끝까지 ..

안녕하세요! 오늘은 BOJ 13335 - 트럭 문제를 풀어볼게요. 문제를 잘 읽어보면, 다음 네 가지 조건을 만족시키면서, 모든 트럭이 다리를 건너는 최단 시간을 구하라고 했네요.N개의 트럭이 순서를 바꾸지 않고 다리를 건넌다.단위길이 w에는 트럭 w대까지 동시에 올라설 수 있다.트럭은 1 단위시간에 1 단위길이만큼만 이동할 수 있다.(동시에 다리 위에 올라서있는 트럭들의 무게의 합) 문제에서 제시해준 예시를 같이 살펴보면서, 어떻게 구현해야 할지 생각해 볼게요. 접근  다리의 길이 w = 2이고, 최대하중 L = 10, 트럭은 {7, 4, 5, 6} 순서로 대기 중인 상황이에요. Step_1)1. 우선 다리 위에는 트럭이 없어요.2. 다리에 진입하지 못한 가장 앞 트럭을 다리로 이동시켜요. (순서를 바..

안녕하세요! 오늘은 BOJ 1038 - 감소하는 수 문제를 풀어볼게요. 접근 문제를 읽어보면, 음이 아닌 정수 (0과 자연수) X의 자릿수가 가장 큰 자릿수부터 가장 작은 자릿수까지 감소만 하는 수가 '감소하는 수'라고 정의했네요.321과 950은 백의 자리부터 일의 자리까지 전부 감소만 하니 감소하는 수지만, 322는 같은 숫자가 있고, 958은 감소하다가 증가했으니 감소하는 수가 아니라고 해요.0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수라고 하네요. 쭉쭉 이어서 써보면, 10이 10번째 감소하는 수가 될 거예요.그리고 11~19는 일의 자리 수가 십의 자리 수보다 크거나 같으니, 20이 11번째 감소하는 수가 되겠네요.21은 12번째 감소하는 수지만, 11~19와 마찬가지로 22~29도 감..

안녕하세요! 오늘은 BOJ 6198 - 옥상 정원 꾸미기 문제를 풀어볼게요. 접근 - Step 1 문제가 굉장히 친절하게 그림까지 그려줘서, 상황에 대한 이해가 어렵진 않을 것 같아요. i번째 빌딩에서는 i번째 빌딩의 오른쪽 빌딩만 볼 수 있고, 자신이 위치한 빌딩보다 높이가 높거나 같은 빌딩의 옥상은 볼 수 없어요.모든 빌딩의 관리인들이 확인할 수 있는 빌딩 수의 합을 구해주는 것이 문제예요.저는 이렇게 추측하고 시작했어요: "빌딩들에 번호가 붙어 있다고 생각을 해보면, 다음으로 들어오는 건물의 높이가 나보다 낮으면 카운팅 해주고, 나보다 높이가 높거나 같은 건물이 들어올 경우에는 카운팅을 중단하면 되지 않을까?" 예시를 한 단계씩 쪼개서 살펴보면서, 어떻게 구현해야 할지 감을 잡아볼게요.  왼쪽 빌딩..

안녕하세요! 오늘은 BOJ 1744 - 수 묶기 문제를 풀어볼게요. 문제를 읽어보면, 길이가 N인 수열에서 위치에 상관없이 두 수를 묶을 수 있고, 묶은 두 수는 곱해서 더한다고 해요.자기 자신을 묶을 수는 없고, 수열의 모든 수는 단 한 번만 묶거나, 묶지 않아야 하고, 이렇게 각 수를 적절히 묶었을 때 합이 최대가 될 때의 합을 구하고 싶대요.수열의 크기 N은 50 이하의 자연수고, 수열의 수가 -1000부터 1000까지니까 아무리 최대한 큰 수끼리 묶어서 더한다고 해도 1000 * 1000 * 25 = 25,000,000 이니까, 정수형 범위 안에 들어옴이 보장되어 있어요. 접근  먼저 문제에서 준 예시부터 살펴볼게요.수열 {0. 1. 2. 4. 3. 5}에서 그냥 더하면 0+1+4+3+5 = 15..