내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/43162

기본적인 DFS로 풀이가능한 문제입니다.

이 문제도 기본유형의 문제라 레벨이 높은 상태인것 같습니다.

아직 탐색하지 않은 computer를 만나면 DFS로 연결된 모든 컴퓨터들을 탐색하고, 방문처리해주면 됩니다.

DFS 한번에 연결된 컴퓨터들이 전부 방문되기 때문에 정답인 네트워크의 갯수는 DFS의 호출횟수와 같습니다.

def solution(n, computers):
    answer = 0
    visited = [False for i in range(n)]

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            findNetwork(i, computers, visited)
            answer += 1

    return answer


def findNetwork(now, computers, visited):
    for next in range(len(computers[now])):
        if computers[now][next] == 1 and not visited[next]:
            visited[next] = True
            findNetwork(next, computers, visited)
            


print(solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]))

https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/

곱이 양의 정수가 되는 가장 긴 부분수열의 길이를 구하는 문제입니다.

고려해야할 조건은 다음과 같습니다.

1. 중간에 0이 들어가는 경우 어떻게 곱해도 0이 되기 때문에 양의 정수라는 조건을 충족시키지 못합니다. 그래서 부분수열은 0을 기준으로 끊어진 형태가 됩니다.

2. 부분수열 안에 음수가 짝수개 있으면 곱하면서 서로 상쇄되어 곱셈의 결과가 양의 정수가 됩니다.

3. 그럼 음수가 홀수개 있다면 어떨까요? 하나만 빼주면 짝수가 됩니다.

(음수가 1개 있어서 하나를 빼도 0개로 조건을 충족합니다.)

내 위치에서 가장 먼 음수를 빼고 그 다음부터 카운트 하는게 수열의 길이를 길게 만들겁니다.

그리고 내 위치에서 가장 먼 음수는 0 이후에 처음 나온 음수가 될겁니다.

코드로 구현하면 이렇습니다.

class Solution:
    def getMaxLen(self, nums: list) -> int:
        answer = -1
        zeroInedx = -1
        firstNegative = -1
        negativeCount = 0
        
        for i in range(0, len(nums)):
            if(nums[i] == 0):
                firstNegative = -1
                negativeCount = 0
                zeroInedx = i
            
            if(nums[i] < 0):
                negativeCount += 1 
                if(firstNegative == -1):
                    firstNegative = i
            
            if(negativeCount % 2 == 0):
                answer = max(answer, i - zeroInedx)
            else :
                answer = max(answer, i - firstNegative)
        
        return answer
    

input = [[1,-2,-3,4],[0,1,-2,-3,-4],[-1,-2,-3,0,1]]

for i in input:
    print(Solution().getMaxLen(i))

https://school.programmers.co.kr/learn/courses/30/lessons/49189

기본적인 BFS로 풀이가 가능한 문제입니다.

기본 문제라 Lv.3로 놓인거지 요즘 레벨로는 2레벨 중에서도 쉬운문제가 아닐까 싶습니다...

node의 갯수가 edge의 갯수보다 훨씬 많기 때문에 인접행렬 대신 인접리스트를 사용해 구현했습니다.

(node의 갯수가 2만개로 인접행렬로는 2만*2만 = 4억 사이즈가 됩니다.)

BFS를 이용해 시작점에서 부터의 거리가 한 칸씩 먼 노드들을 탐색했고, 매번 탐색한 노드의 갯수를 저장해서

더 탐색할 노드가 없는 경우엔 이전 턴에 탐색한 노드의 갯수를 리턴했습니다.

from collections import deque


def solution(n, edge):
    answer = 0
    adjList = [[] for i in range(n+1)]
    visited = [False]*(n+1)
    
    for i in edge:
        start = i[0]
        end = i[1]
        
        adjList[start].append(end)
        adjList[end].append(start)
    
    queue = deque()
    queue.append(1)
    visited[1] = True

    while(len(queue) != 0):
        answer = size = len(queue)
        
        for i in range(size):
            start = queue.popleft()
            
            for e in adjList[start]:
                if(not visited[e]):
                    visited[e] = True
                    queue.append(e)
    
    return answer


n = 6
vertexs = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

print(solution(n,vertexs))

https://leetcode.com/problems/maximum-sum-circular-subarray/

Maximum Subarray를 살짝 비튼 문제입니다.

처음엔 Maximum Subarray를 앞 뒤로 두번 구해서 겹치지 않도록 조각을 붙여가며 탐색할까 생각도 해봤지만 깔끔한 구현방법이 떠오르지 않아서 솔루션을 참고했습니다.

생각지도 못했던 아이디어가 있더라구요.

https://leetcode.com/problems/maximum-sum-circular-subarray/discuss/178422/One-Pass

자세한 설명은 위 링크에 있는데 핵심 아이디어는 이미지만 봐도 알 수 있으실것 같습니다.

자명하게도 최대합이 되는 부분수열은 두 경우중에 하나일겁니다.

원형으로 이어지지 않거나, 이어지거나.

이어지지 않는 경우는 기존의 Maximum Subarray문제의 풀이와 같습니다.

이어지는 경우는 위 그림처럼 전체 합에서 Minimum Subarray를 뺀 값이 됩니다.

다시 생각해보면 원형으로 이어진 이 Maximum Subarray는 아래의 array의 Maximum Subarray와 같습니다.

(왼쪽 부분을 똑 떼어서 붙였습니다.)

array를 두 부분으로 나누었을 때, 한쪽이 최대합이라면 반대쪽은 최소합이 됩니다.

totalSum - maxSum = minSum / totalSum - minSum = maxSum

만약 더 작은 음수의 다른 minSum이 존재한다면 maxSum도 더 큰 수가 생겨서 수식에 모순이 생기게 됩니다.

array의 모든 수가 양수여서 minSum이 없는 경우에는 배열의 전체 totalSum이 문제의 해답이 되고, 케이스 1에서 찾아낼 수 있습니다.

즉 array의 minSum을 찾아 totalSum에서 뺀다면 원형으로 이어진 maxSum을 알아낼 수 있습니다.

minSum을 찾는 메소드를 따로 작성해도 되지만 기존의 메소드를 이용하되 입력 배열의 부호를 바꿔주면 똑같이 구할 수 있습니다. 다만 모든 수가 음수인 경우(minSum == totalSum)에는 예외가 발생하므로 그 부분만 따로 처리해주시면 됩니다.

class Solution:
    def maxSubarraySumCircular(self, nums: list) -> int:
        nonCircularSum = self.maxSubArray(nums)
        circularSum = sum(nums)
        
        for i in range(0,len(nums)):
            nums[i] = -nums[i]
        
        circularSum += self.maxSubArray(nums)
        
        return max(nonCircularSum,circularSum) if(circularSum != 0) else nonCircularSum
    
    def maxSubArray(self, nums: list) -> int:
        sum = -100_000
        maxSum = -100_000
        for i in nums:
            if(i > i + sum):
                sum = i
            else:
                sum += i
                
            maxSum = max(sum, maxSum)
                
        return maxSum

input = [[1,-2,3,-2],[5,-3,5],[-3,-2,-3]]
for i in input:
    print(Solution().maxSubarraySumCircular(i))

https://leetcode.com/problems/maximum-subarray/

연속 부분 수열의 최대합(한국어로 맞는지 모르겠습니다)을 구하는 정말 유명한 DP 문제입니다.

문제를 볼 때마다 매번 10초 정도 LCS와 헷갈립니다. 완전히 다른 알고리즘이라 금방 깨닫긴 하지만, 아마 입력의 형태가 비슷해서 그런것 같습니다. 

저만 그럴수도 있구요.

아이디어는 이렇습니다. 배열 nums가 주어졌다고 할때, 

어떤 위치 i 에서 끝나는 부분수열의 최대합은 두가지 경우입니다.

i-1에서 끝나는 부분수열의 최대합이 양수라서 그 값을 더하거나, 버리고 자기 자신만 취하거나

배열을 만들어서 각 위치마다 해당 위치에서 끝나는 최대합을 기록하며 풀이해도 되는데 이번 문제에선 중간 내용을 활용하지 않기 때문에 그냥 변수에 바로 저장해서 풀이했습니다.

if-else구문을 max(i, sum+i)로 줄이면 코드라인은 줄어들지만 실행시간이 조금 느려집니다.

조건문을 (0 > sum)으로 작성해도 같은 코드입니다.

class Solution:
    def maxSubArray(self, nums: list) -> int:
        sum = -100_000
        maxSum = -100_000
        for i in nums:
            if(i > i + sum):
                sum = i
            else:
                sum += i
                
            maxSum = max(sum, maxSum)
                
        return maxSum

input = [[-2,1,-3,4,-1,2,1,-5,4],[1],[5,4,-1,7,8]]
for i in input:
    print(Solution().maxSubArray(i))

https://leetcode.com/problems/jump-game-ii/

점프게임의 시리즈 문제입니다.

1번 문제와 달리 도달할 수 있는지의 가부가 아니라 도달하는 최소의 step을 리턴해야 합니다. (마지막 위치에 도달하는것은 문제에서 보장함.)

처음에는 각 index별로 도달하는 최소의 step을 갱신하는 기본적인 DP의 풀이방법으로 풀었는데, 채점에 통과는 되었지만 실행시간이 좋지 않았습니다.

제공되는 testcase의 내용을 확인해 보니 각 index에서 매 번 목적지에 도달이 가능하다면 1차 제출한 코드는 N^2의 시간복잡도를 갖게 된다는 사실을 알게되었습니다.

(예를 들어 100 길이의 배열에 들어있는 숫자가 99,98,97,96...0 이라면 제 코드는 index를 한 칸 진행할 때마다 뒤의 모든 배열을 순회해야 합니다.)

class Solution:
    def jump(self, nums: list) -> int:
        dp = [20000]*len(nums)
        dp[0] = 0
        
        for i in range(0, len(nums)-1):
            for j in range(i+1, min(len(nums), i + nums[i] + 1)):
                dp[j] = min(dp[i]+1, dp[j])
        return dp[-1]
    

input = [[2,3,1,1,4],[2,3,0,1,4]]

for i in input:
    print(Solution().jump(i))

토론 창의 도움을 얻어 BFS와 유사한, 매 step마다 내가 갈수있는 최대의 범위를 갱신하는 코드를 작성했습니다.

class Solution:
    def jump(self, nums: list) -> int:
        step = 0
        position = 0
        canMove = 0
        
        while(position < len(nums)-1):
            step += 1
            maxMove = 0
            
            while(position <= canMove):
                maxMove = max(maxMove, position+nums[position])
                position += 1
                if(maxMove >= len(nums)-1):
                    return step
                
            canMove = maxMove
        
        return step

input = [[0],[2,3,1,1,4],[2,3,0,1,4]]

for i in input:
    print(Solution().jump(i))

확실히 실행시간이 어마어마하게 차이가 나네요.

https://leetcode.com/problems/jump-game/

배열의 마지막에 도달할 수 있는지 묻는 문제입니다.

저는 거꾸로 배열의 마지막에서 시작해 어떤 위치까지 갈 수 있는지의 여부를 갱신하고 만약 시작점에서도 가능하다면 True를 리턴하는 식으로 풀이했습니다.

class Solution:
    def canJump(self, nums: list) -> bool:
        idx = len(nums)-2
        reach = len(nums)-1
        
        while(idx >= 0):
            if(nums[idx] + idx >= reach):
                reach = idx
            idx -= 1
            
        return reach == 0
    

input = [[2,3,1,1,4],[3,2,1,0,4],[2,0,0]]

for i in input:
    print(Solution().canJump(i))

https://www.acmicpc.net/problem/17472

다리만들기 1과는 비슷한듯 전혀 다른 문제입니다.

각 섬들을 다리로 연결하는 부분은 같지만, 다리만들기1 문제와 다르게 다리는 직선으로만 가능하며 모든 섬이 연결되도록 완성해야 하고 이때 다리의 길이가 2이상인 최소한의 다리를 활용해야 합니다.

이 문제는 크게 3가지 과정으로 나눌 수 있습니다.

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 최단 다리를 모두 만들기

3. 다리를 선택해 모든 섬들이 연결되게 만들기.

1,2번 과정은 다리만들기 1번 문제와 비슷하고 3번 과정은 MST(최소 스패닝 트리)를 구하는 과정으로 만들 수 있습니다.

즉, 각각의 섬들이 노드가 되고 각 섬들에서 다른섬으로 연결되는 최소거리의 다리가 엣지가 되는 식입니다.

MST를 만드는 알고리즘은 여러 종류가 있는데 우선순위 큐와 Union만을 이용해 간단하게 구현할 수 있는 크루스칼(Kruskal) 알고리즘을 사용했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class q17472__BOJ_다리만들기2 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[] parent;
	static int N, M;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		int[][] map = new int[N][M];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < M; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;
		Queue<int[]> queue = new LinkedList<>();

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < M; m++) {
				if (map[n][m] == -1) {
					queue.offer(new int[] { n, m });
					map[n][m] = island;

					while (!queue.isEmpty()) {
						int[] now = queue.poll();
						int x = now[0];
						int y = now[1];

						for (int i = 0; i < 4; i++) {
							int nX = x + delta[i][0];
							int nY = y + delta[i][1];
							if (isIn(nX, nY) && map[nX][nY] == -1) {
								queue.offer(new int[] { nX, nY });
								map[nX][nY] = island;
							}
						}
					}
					island++;
				}
			}
		}

		int[][] graph = new int[island][island];

		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][M];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < M; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m, 0, 5 });
						visit[n][m] = true;
					}
				}
			}

			while (!queue.isEmpty()) {
				int[] now = queue.poll();
				int x = now[0];
				int y = now[1];
				int l = now[2];
				int dir = now[3];

				if (dir == 5) {
					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY] && map[nX][nY] == 0) {
							queue.offer(new int[] { nX, nY, l + 1, i });
							visit[nX][nY] = true;
						}
					}
				}

				else {
					int nX = x + delta[dir][0];
					int nY = y + delta[dir][1];
					if (isIn(nX, nY) && !visit[nX][nY]) {

						if (map[nX][nY] == 0) {
							queue.offer(new int[] { nX, nY, l + 1, dir });
							visit[nX][nY] = true;
						} else {
							if (graph[is][map[nX][nY]] == 0 && 1 < l) {
								graph[is][map[nX][nY]] = l;
							}
							visit[nX][nY] = true;
						}
					}
				}
			}
		}

		int answer = 0;
		parent = new int[island];
		for (int n = 1; n < island; n++) {
			parent[n] = n;
		}
		PriorityQueue<int[]> pqueue = new PriorityQueue<>((e1, e2) -> {
			return e1[0] - e2[0];
		});

		for (int from = 1; from < island; from++) {
			for (int to = 1; to < island; to++) {
				if (graph[from][to] != 0) {
					pqueue.offer(new int[] { graph[from][to], from, to });
				}
			}
		}

		while (!pqueue.isEmpty()) {
			int[] now = pqueue.poll();
			int l = now[0];
			int from = now[1];
			int to = now[2];

			if (find(from) != find(to)) {
				answer += l;
				union(from, to);
			}
		}

		boolean flag = false;
		int parent = find(1);
		for (int n = 1; n < island; n++) {
			if (find(n) != parent) {
				flag = true;
				break;
			}
		}

		if (flag) {
			System.out.println(-1);
		} else {
			System.out.println(answer);
		}
	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < M) {
			return true;
		}
		return false;
	}

	static int find(int i) {
		if (i == parent[i])
			return i;
		return parent[i] = find(parent[i]);
	}

	static void union(int x, int y) {
		x = find(x);
		y = find(y);

		if (x > y)
			parent[x] = y;
		else
			parent[y] = x;
	}
}

https://www.acmicpc.net/problem/2146

구현을 신경써야 하는 문제입니다.

문제를 2개의 과정으로 나눌 수 있습니다.

1. 주어진 지도에서 섬의 영역을 확인하고 이름 붙이기

2. 각각의 섬에서 다른 섬으로 잇는 다리 만들기

1번은 BFS DFS아무것이나 원하는 방법으로 구현하면 됩니다.

2번의 경우는 BFS를 이용하는것이 구현과 이해가 간편합니다.

시간 단축을 위해서는 모든 경우에 대해 다리를 구하고 다리의 길이를 비교하는 것 보다는 최소값을 다리가 완성될 때 마다 갱신하고, 이미 구해진 최솟값을 넘는 경우에는 Queue를 비워버리고 스킵하는 것이 훨씬 빠릅니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class q2146_BOJ_다리만들기 {
	static StringTokenizer st;
	static int[][] delta = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	static int[][] map;
	static int[] parent;
	static int N;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());

		map = new int[N][N];

		for (int n = 0; n < N; n++) {
			st = new StringTokenizer(br.readLine());
			for (int m = 0; m < N; m++) {
				map[n][m] = Integer.parseInt(st.nextToken()) * -1;
			}
		}

		int island = 1;

		for (int n = 0; n < N; n++) {
			for (int m = 0; m < N; m++) {
				if (map[n][m] == -1) {
					dfs(n, m, island);
					island++;
				}
			}
		}

		int answer = Integer.MAX_VALUE;
		Queue<int[]> queue = new LinkedList<>();
		for (int is = 1; is <= island; is++) {
			boolean[][] visit = new boolean[N][N];

			for (int n = 0; n < N; n++) {
				for (int m = 0; m < N; m++) {
					if (map[n][m] == is) {
						queue.offer(new int[] { n, m });
						visit[n][m] = true;
					}
				}
			}

			int l = 0;

			while (!queue.isEmpty()) {
				int size = queue.size();

				for (int s = 0; s < size; s++) {

					int[] now = queue.poll();
					int x = now[0];
					int y = now[1];

					for (int i = 0; i < 4; i++) {
						int nX = x + delta[i][0];
						int nY = y + delta[i][1];
						if (isIn(nX, nY) && !visit[nX][nY]) {

							if (map[nX][nY] == 0) {
								queue.offer(new int[] { nX, nY });
								visit[nX][nY] = true;
							} else {
								answer = Math.min(answer, l);
								visit[nX][nY] = true;
							}
						}
					}
				}
				l++;
				if (l > answer) {
					queue.clear();
				}
			}
		}
		System.out.println(answer);

	}

	static void dfs(int x, int y, int name) {
		map[x][y] = name;

		for (int i = 0; i < 4; i++) {
			int nX = x + delta[i][0];
			int nY = y + delta[i][1];
			if (isIn(nX, nY) && map[nX][nY] == -1) {
				dfs(nX, nY, name);
			}
		}

	}

	static boolean isIn(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N) {
			return true;
		}
		return false;
	}
}

https://leetcode.com/problems/delete-and-earn/

주어진 조건에서 어떤 숫자를 선택하면 앞 뒤로 붙은 숫자들은 선택할 수 없습니다.

또 어떤 숫자를 선택하면 그 숫자는 계속 선택해도 됩니다.

문제의 설명만 보면 숨겨진 의도를 바로 찾기 힘들지만 생각해 보면 숫자를 연달아 선택할 수 없다는건 이전의 House Robber문제와 같은 유형이란것을 알 수 있습니다.

또 어떤 숫자를 선택하면 그 숫자에 걸린 point는 모두 획득 할 수 있기 때문에 숫자의 범위와 같은 크기의 List로 값을 압축 해 쉽게 구현 할 수 있습니다.

class Solution:
    def deleteAndEarn(self, nums: list) -> int:
        expectValue = [0] * 10001
        for i in nums:
            expectValue[i] += i
        
        dp = [0] * 10001
        dp[1] = expectValue[1]
        for i in range(2,10001):
            dp[i] = max(dp[i-1], dp[i-2]+expectValue[i])
        
        return dp[-1]
    

input = [[3,4,2], [2,2,3,3,3,4]]
for i in input:
    print(Solution().deleteAndEarn(i))

https://leetcode.com/problems/house-robber-ii/

https://nodingco.tistory.com/101?category=570522 

위 문제의 시리즈로 마찬가지로 DP문제입니다.

집들의 위치가 원형으로 연결되어 첫번째 집과 마지막 집이 붙어있는 형태가 되었다는 조건이 추가되었습니다.

아이디어를 떠올리기가 힘들었는데요. 

간단하게 생각하면 첫번째 집과 마지막 집은 동시에 도둑질을 할 수 없습니다.

집들을 의미하는 입력 리스트를 [첫번째 집~마지막 앞의 집]과 [두번째 집~마지막 집]으로 나누어 각각의 최댓값을 1번 문제와 같은 방식으로 구하면 둘 중에 더 큰 값이 정답이 됩니다.

생각해보면, [첫번째 집~마지막 앞의 집]에서 나오는 정답의 경우는 두가지로 생각해 볼 수 있습니다.

1. 첫번째 집을 도둑질 함 -> 이 경우엔 마지막 집은 당연히 털 수 없었습니다. 하지만 마지막 집을 턴 경우의 값이 더 컸을수도 있겠죠? 그 경우는 [두번째 집~마지막 집]으로 나뉜 범위에서 구한 정답이 됩니다.

2. 첫번째 집을 도둑질 하지 않음 - > 이 경우는 [두번째 집~마지막 집]으로 나눈 것에서 얻어낸 정답과 같습니다. (마지막집의 도둑질여부는 관계없습니다.)

[두번째 집~마지막 집]의 경우도 같은 방식으로 생각됩니다.

따라서 두 범위에서 문제를 풀이하면 둘 중 하나는 무조건 정답이 되게 됩니다.

class Solution:
    def rob(self, nums: list) -> int:
        if(len(nums) == 1):
            return nums[0]
        
        return max(self.sliceRob(nums[1:]), self.sliceRob(nums[:-1]))

    def sliceRob(self, nums: list) -> int:
        dp = [0] * (len(nums) + 1)
        dp[0] = 0
        dp[1] = nums[0]

        for i in range(2, len(nums)+1):
            dp[i] = max(dp[i-1],dp[i-2]+ nums[i-1])

        return dp[-1]


input = [[2,3,2],[1,2,3,1],[1,2,3],[1]]
for i in input:
    print(Solution().rob(i))

https://leetcode.com/problems/house-robber/

DP의 대표적인 유형 입문 문제입니다.

집을 연속으로 털지 못한다는 것에서 N번째 집을 털때의 최대값은 N-2번째 집을 털고 N번째 집을 터는 것과 N번째 집을 털지 않는 경우 (즉 N-1번째 집에서의 최댓값) 두 값중 큰 값을 고르게 됩니다.

class Solution:
    def rob(self, nums: list) -> int:
        
        dp = [0] * (len(nums) + 1)
        dp[0] = 0
        dp[1] = nums[0]

        for i in range(2, len(nums)+1):
            dp[i] = max(dp[i-1],dp[i-2]+ nums[i-1])

        return dp[-1]


input = [[1,2,3,1],[2,7,9,3,1],[1]]
for i in input:
    print(Solution().rob(i))