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

프로그래머스 - 부대복귀 # 조건 강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다. 강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을..

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

프로그래머스 - 단속 카메라 # 조건 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다. 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니..

백준 18500 - 미네랄 2 시간 제한 1초, 메모리 제한 512MB # 조건 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다. 막대를 던지기 전에 던질 높이를 정해야 한다. 막대는 땅과 수평을 이루며 날아간다. 막대가 날아가다..

백준 22955 - 고양이 도도의 탈출기 시간 제한 5초(추가 시간 x), 메모리 제한 1024MB(추가 메모리 x) # 조건 고양이 도도가 강아지들을 피해 탈출구를 찾아 방을 탈출하려 하고 있다. 고양이 도도는 현재 위치한 공간의 상태에 따라 다음과 같이 움직일 수 있다. 고양이가 위치한 곳에 사다리가 존재하거나 고양이가 위치한 곳이 아래가 뚫려있는 공간이 아닌 상태에서 고양이가 위치한 곳의 아래 칸에 사다리가 존재한다면 각각 위 칸과 아래 칸으로 이동할 수 있고 사다리를 이용하여 한 칸 이동할 시 5만큼의 체력이 소모된다. 고양이가 위치한 곳이 아래가 뚫려 있는 공간이라면 고양이는 아래에 있는 바닥 중 가장 처음 마주한 바닥에 착지하게 되며 이때 10만큼의 체력이 소비된다. 고양이가 아래가 뚫려 있는..

프로그래머스 - 표 병합 # 조건 당신은 표 편집 프로그램을 작성하고 있습니다. 표의 크기는 50 × 50으로 고정되어있고 초기에 모든 셀은 비어 있습니다. 각 셀은 문자열 값을 가질 수 있고, 다른 셀과 병합될 수 있습니다. 위에서 r번째, 왼쪽에서 c번째 위치를 (r, c)라고 표현할 때, 당신은 다음 명령어들에 대한 기능을 구현하려고 합니다. "UPDATE r c value" (r, c) 위치의 셀을 선택합니다. 선택한 셀의 값을 value로 바꿉니다. "UPDATE value1 value2" value1을 값으로 가지고 있는 모든 셀을 선택합니다. 선택한 셀의 값을 value2로 바꿉니다. "MERGE r1 c1 r2 c2" (r1, c1) 위치의 셀과 (r2, c2) 위치의 셀을 선택하여 병합합..

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

백준 17780 - 새로운 게임 시간 제한 0.5초, 메모리 제한 512MB # 조건 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판 모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있..