백준 1182 - 부분수열의 합 시간 제한 2초, 메모리 제한 256MB # 조건 N개의 정수로 이루어진 수열이 있을 떄, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. # 접근 방법 조합을 이용하여 풀어주면 된다. 순서가 상관이 없으므로 itertools 라이브러리의 combination을 이용해준다. 범위를 1 ~ N+1 까지 돌리면서 조합의 ..

백준 1515 - 수 이어 쓰기 시간 제한 2초, 메모리 제한 128MB # 조건 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다. 세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다. 남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.) # 접근 방법 현재 주어진 남은 수가 하나씩 등장할 동안 num을 1씩 증가시키며 확인해준다. nums = input() i = 0 while T..

백준 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) 위치의 셀을 선택하여 병합합..