백준 12026 - BOJ 거리 시간 제한 2초, 메모리 제한 512MB # 조건 BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다. 스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다. BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다. 스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k * k이다. 스타트는 BOJ를 외치면서 링크를 만나..

[백준 11052 - 카드 구매하기](https://www.acmicpc.net/problem/11052 시간 제한 1초, 메모리 제한 256MB # 조건 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving) 분야에서 유명한 사람들의 아이디어와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같은 8가지가 있다. 전설카드, 레드카드, 오렌지카드, 퍼플카드, 블루카드, 청록카드, 그린카드, 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 ..

백준 1309 - 동물원 시간 제한 2초, 메모리 제한 128MB # 조건 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다. 동물원 조련사의 머리가 아프지 않도록 우리가 2N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다. 입력 첫째 줄에 우리의 크기 N(1 1 + 4 + 2가 된다. 즉, 새로운 우리 한 줄을 추가하게 되면 더해지는 경우의 수는 사자를 놓는 경우와 사자를 놓지 않는 경우로 나..

프로그래머스 - 코딩 테스트 공부 # 조건 당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다. 알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다. 문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다. 예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라고 가정해보겠습니다. A라는 문제가 알고력 10, 코딩력 10을 요구한다면 A 문제를 풀 수 있습니다. B라는 문제가 알고력 10, 코딩력 20을 요구한다면 코딩력이 부족하기 때문에 B 문제를 풀 수 없습니다. 풀 수 없는 문제를 해결하기 위해서는 알고력..

백준 1937 - 욕심쟁이 판다 시간 제한 2초, 메모리 제한 256MB # 조건 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 판다가 최대한 많은 칸을 방문할 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 것이다. n × n 크기의 대나무..

백준 1099 - 알 수 없는 문장 시간 제한 2초, 메모리 제한 128MB # 조건 형택이와 그의 친구들은 자꾸 다른 사람들이 대화를 엿듣는 것이 짜증났다. 따라서, 새로운 언어를 만들었다. 이 언어에는 단어가 N개 있다. 그리고 이 언어의 문장은 단어를 공백없이 붙여쓴 것이다. 이 문장에서 각 단어는 0번 또는 그 이상 나타날 수 있다. 이 언어가 형택스러운 이유는 (특별한 이유는) 단어에 쓰여 있는 문자의 순서를 바꿔도 되기 때문이다. 이때, 원래 단어의 위치와 다른 위치에 있는 문자의 개수 만큼이 그 순서를 바꾼 단어를 만드는 비용이다. 예를 들어, abc란 단어가 있을 때, abc는 비용 0으로 만들 수 있고, acb, cba, bac는 비용 2로 바꿀 수 있고, bca, cab는 비용 3으로 ..

백준 1912-연속합 시간 제한 1초, 메모리 제한 128MB # 조건 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. # 접근 방법 누적 합과 비슷하게 풀면 되지만 음수가 존재한다. 따라서 DP를 이용하여 풀어준다. NUMS 를 입력받은 후 최소 1개의 수를 선택해야 하므로 0번 인덱스를 선택한 것을 기본값으로 한다. 1부터 N까지 순회하는데 nums[i] = max(nums[i], nums[i-1] + nums[..

백준 26093 - 고양이 목에 리본 달기 시간 제한 1초(추가 시간 없음), 메모리 제한 1024MB(추가 메모리 없음) # 조건 외로운 윤제는 고양이를 키우기로 했다. N 마리의 고양이를 입양하기로 한 윤제는 고양이들에게 리본을 달아주기 위해 $K$ 종류의 리본을 충분히 준비했다. 즉, 각 리본의 개수는 무한하다. 각 고양이마다 리본의 종류에 따라 좋아하는 정도가 다르고, 이를 만족도로 나타낼 수 있다. 고양이들을 번호순으로 한 줄로 세우고 리본을 달아주려고 하는데, 각 고양이는 자신과 이웃한(왼쪽 혹은 오른쪽) 고양이와 같은 종류의 리본을 다는 것을 굉장히 싫어한다. 윤제는 고양이들이 싫어하는 상황을 피하면서 각 고양이의 리본에 대한 만족도의 총합을 극대화하고 싶다. 이 조건을 만족하는 만족도 합의..

백준 27971 - 강아지는 많은수록 좋다 시간 제한 2초, 메모리 제한 1024MB # 조건 마법소녀 마도카의 고양이에 깊은 감명을 받은 마법소녀 호무라는 자신도 마법을 이용하여 강아지 N마리를 집에서 키우기로 결심했다! 호무라는 한 번의 행동에서 다음 2가지 마법 중 하나를 선택하여 사용한다. 가장 처음에는 호무라의 집에 강아지가 존재하지 않는다. A마법 - 강아지 A마리를 호무라의 집에 생성한다. B마법 - 강아지 B마리를 호무라의 집에 생성한다. 그러나 미숙한 마법 사용은 호무라에게 추가적인 제약 사항을 주게 되었다. 만약 호무라의 방에 생성된 강아지의 수가 M개의 닫힌 구간들 [L1, R1], [L2, R2], ... [Lm, Rm] 중 하나 이상에 포함되게 된다면, 그 즉시 방에 생성된 모든 ..