하늘을 날고 싶은 펭귄

[백준, 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..

안녕하세요! 오늘은 BOJ 11559 - Puyo Puyo 문제를 풀어볼게요.  뿌요뿌요라는 게임에 대해서 알고 계신가요?떨어지는 (슬라임처럼 생긴) 뿌요들을 쌓아서, 같은 색깔의 뿌요를 4개 쌓으면 '연쇄'가 일어나 뿌요들이 사라지고 상대방을 공격하는 대전 게임이에요.실제 게임에서는 위에서 랜덤 하게 뿌요가 떨어지고, 상대방을 방해하는 요소도 있는 걸로 알고 있는데요.이 문제는 그런 것은 배제하기로 하고, 주어진 상황에서 얼마나 연쇄가 일어나는지에 대해서 구해야 하는 문제예요. 접근 - (1) 규칙 파악 우선 문제에서 준 뿌요뿌요의 룰 5가지를 한 가지씩 차근차근 살펴볼게요. 첫 번째로, 뿌요는 중력의 영향을 받아서 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어져요.그림과 같이 뿌요 아래에 빈 공간이 ..

안녕하세요! 오늘은 BOJ 11399 - ATM 문제를 풀어볼게요. 문제를 읽어보면, 이 문제는 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구하는 문제예요. 접근 문제에 있는 예시를 보고 접근해 볼게요. 첫 번째 예시에서는 [1, 2, 3, 4, 5] 순서로 줄을 섰어요.맨 처음 사람이 1번 사람이니, 3분이 필요해서 뒷사람 모두가 3분이 누적돼요. 두 번째 예시에서는 [2, 5, 1, 4, 3] 순서로 줄을 섰어요.맨 처음 사람이 2번 사람이니, 1분이 필요해서 뒷사람 모두가 1분을 누적돼요.여기에서 최종적으로 걸리는 시간의 합이 사람들이 줄을 서는 순서에 따라 달라짐을 알 수 있어요. 첫 번째 사람에 대해서만 언급했지만, 두 번째 사람도 시간이 짧게 걸리는 사람이 와야 두 번째 사람부터..