Jenikeju

내가 푼 풀이

- 주어진 레벨을 배열로 만들었을때 원소가 중복되지 않으며, 오름차순으로 만들어야 한다.

- 주어진 배열의 인덱스순으로 난이도가 오름차순이므로, 정렬하지 않고 마지막 어려운 레벨부터 점수를 수정한다.

- 현재 레벨이 이전 레벨보다 점수가 작거나 같으면 이전레벨의 점수를 현재레벨의 점수 - 1로 바꾸고,

- 이전레벨의 점수 - 현재레벨의 점수 + 1 해준다.

- 이를 배열의 첫 번째 원소까지 모두 해주면, 원소가 중복되지 않는 오름차순으로 만들어진다.

import Foundation

let count = Int(readLine()!)!
var arr = [Int]()
var result = 0

// 레벨 점수 입력
for i in 0..<count {
    arr.append(Int(readLine()!)!)
}

// 마지막레벨부터 검사한다.
// 현재레벨이 이전레벨보다 점수가 낮거나 같으면 수정
// 이전레벨의 점수 = 현재레벨의 점수 - 1
// 점수감소횟수 = 이전레벨의 점수 - 현재레벨의 점수 + 1
for i in (1..<arr.count).reversed() {
    if arr[i] <= arr[i-1] {
        result += arr[i-1] - arr[i] + 1
        arr[i-1] = arr[i] - 1
    }
}

print(result)

- 수열이 주어졌을 때, 각 위치 인덱스에서 만들 수 있는 바이토닉 수열의 길이 최댓값을 출력한다.

- dp[i] = j : i번째 인덱스의 원소값을 기준으로 했을 때의 증가하는 수열의 길이

- rdp[i] = j : i번째 인덱스의 원소값을 기준으로 i+1 이후로 감소하는 수열의 길이

예시

arr = [1,2,1,5]

- index = 0인 원소 1이 주어졌을 때, 1 자체로 수열의 길이 1을 가진다. dp[0] = 1

- index = 1인 원소 2가 주어졌을 때, 2 자체로 수열의 길이 1을 가진다. dp[1] = 1

- arr[0] = 1은 2보다 작은 값이다.

- 인덱스 1 이전의 원소중 중복되는 작은 수가 없다. 

- dp[1] = dp[1] + 1

- index = 2인 원소 1이 주어졌을 때, 1 자체로 수열의 길이 1을 가진다. dp[2] = 1

- arr[0] = 1은 같은 값이므로 패스한다.

- arr[1] = 2는 큰 값이므로 패스한다.

- 인덱스 2 이전의 원소중 작은 값이 없다.

- index = 3인 원소 5가 주어졌을 때, 5 자체로 수열의 길이 1을 가진다. dp[3] = 1

- arr[0] = 1은 5보다 작은 값이다.

- 0번째 인덱스 이전의 값이 없으므로 dp[3] = dp[3] + 1 (dp[3] = 2)

- arr[1] = 2는 5보다 작은 값이다.

- 1번째 인덱스 이전의 값 중 2와 중복된 수가 없으므로 dp[3] = dp[3] + 1 (dp[3] = 3)

- arr[2] = 1은 5보다 작은 값이다.

- 2번째 인덱스 이전의 값 중 = arr[2] 이므로 중복된 수로 dp값을 증가시키지 않는다.

위 예시를 통해 조건을 다음과 같이 구현할 수 있다.

1. 이전 인덱스의 원소보다 큰가?

2. 이전 인덱스의 작은 원소들 중 중복되지 않는가?

dp[i] = j 라 했을 때, i번째 원소를 기준으로 증가하는 수열의 길이를 넣었으므로

중복되는지 체크하려면, dp[j] + 1 > dp[i] 이어야 한다.

위 예시에서 arr[3] = 5에서 확인할 때, 0번째 인덱스에서 이미 dp값을 증가시켰으므로 5를 기준으로 한 증가수열에 이미 1이 들어가 있다.

그러고 2번째에서 다시 1을 만났을 때, 이미 중복되므로 dp값을 증가시키지 않았다.

바이토닉수열은 어떤 수 기준으로 증가수열과 감수수열을 합친 것이므로, 위 순서를 역순으로 하면 감소하는 수열이 나온다.

증가수열 + 감소수열을 해준 후, 이는 기준이 되는 수가 중복으로 들어가 있으므로 -1을 해주고 결과 중 최댓값을 출력한다.

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: 0, count: count)
var rdp = Array(repeating: 0, count: count)

// 각 위치의 원소는 그 원소 하나 자체로 바이토닉 수열의 길이 1을 가진다.
// 인덱스 하나를 기준으로 이전 인덱스의 원소들을 모두 검사한다.
// 이전 원소보다 크고, 작은 원소가 중복되지않는 경우 1을 추가해준다.
for i in 0..<dp.count {
    dp[i] = 1
    for j in 0..<i {
        if arr[i] > arr[j] && dp[i] < dp[j] + 1 {
            dp[i] += 1
        }
    }
}

// 위 dp는 증가하는 수열의 길이를 구했다면, rdp는 감소하는 수열의 길이를 구하는것이다.
for i in (0..<rdp.count).reversed() {
    rdp[i] = 1
    for j in (i..<rdp.count).reversed() {
        if arr[i] > arr[j] && rdp[i] < rdp[j] + 1 {
            rdp[i] += 1
        }
    }
}

// 한 원소를 기준으로 했을때, dp rdp를 모두 구하고 더하면 기준이되는 원소가 중복으로 더해지므로 -1을 해준다.
for i in 0..<dp.count {
    dp[i] += rdp[i] - 1
}
print(dp.max()!)

내가 푼 풀이

- 팰린드롬은 주어진 문자가 뒤집어도 같은 문자가 된다면 그 문자열은 팰린드롬인 문자열이다.

- 문자열이 주어졌을때, 이것을 조합해서 만들 수 있는 팰린드롬 문자열은 1개 이상일 수 있다.

- 정답이 여러개면 사전순으로 앞서는 것을 출력한다.

- 팰린드롬인 조건을 여러 가지 생각했었는데, 단순히 만들어보기로 했다.

- 문자열이 주어졌을 때 문자로 쪼갠 후 사전순으로 오름차순으로 정렬한다.

- 문자열의 개수를 Dictonary에 저장해서 개수가 2개이상이라면 2로 나눈 몫만큼 앞뒤로 붙인다.

- 갯수가 홀수라면 문자를 붙이고도 남으니 중간위치에 넣는다.

- 주어진 문자열을 사전순으로 정렬했으니, 문자를 모두 붙여도 만약 팰린드롬 문자열이면 사전순으로 가장 앞서는 문자가 될 것이다.

- 만든 문자열을 뒤집어서 서로 비교했을 때, 같은 문자열이면 팰린드롬 문자열이므로 출력, 다르다면 "I'm Sorry Hansoo"를 출력

import Foundation

var arr = Array(readLine()!).map{ String($0) }
var dict = [String: Int]()
var first = [String]()
var middle = [String]()
var last = [String]()

// 팰린드롬 문자열은 중간을 기준으로 데칼코마니형태를 이루고있다.
// 앞 범위의 문자, 뒤 범위의 문자, 중간 기준이되는 문자 배열 3가지를 선언
// 주어진 문자열을 문자로 쪼갰을때, 문자의 갯수를 dict에 저장
for i in 0..<arr.count {
    if dict[arr[i]] == nil {
        dict[arr[i]] = 1
    } else {
        dict[arr[i]]! += 1
    }
}

// 문자의 사전순으로 정렬한다.
var sortedDict = dict.sorted{ $0.key < $1.key }

// 문자가 2개이상이면 2로 나눈 몫만큼 앞 뒤로 붙여준다.
// 붙이고 나서 문자가 남으면 중간에 붙여준다.
// 문자가 애초에 1개밖에없다면 중간에 붙여준다.
for (key, value) in sortedDict {
    if value > 1 {
        var n = value / 2
        var str = ""
        for i in 0..<n {
            str += key
        }
        first.append(str)
        last.insert(str, at: 0)
        if value % 2 != 0 {
            middle.append(key)
        }
    } else {
        middle.append(key)
        continue
    }
}

// 사전순으로 문자를 붙인 문자열을 뒤집어서 같다면 팰린드롬 문자열
var str = (first + middle + last).joined(separator: "")
if str == String(str.reversed()) {
    print(str)
} else {
    print("I'm Sorry Hansoo")
}

내가 푼 풀이

- 주어진 N의 길이의 오르막 수를 구하는 문제

- 오르막수는 수가 오름차순이면되고, 같은 번호여도 오름차순으로 친다.

- N이 1 일때, 앞자리수 0~9 는 모두 오르막수가 된다. 총 10개

- N이 2일때, 앞자리수와 같거나 큰수가 뒤에 올 수 있다.

- N이 3일때, 마지막수는 그 전의 수보다 같거나 작아야한다.

- 예시로 00 다음에 올 수는 0~9 , 05 다음에 올 수는 5~9 가된다.

- 이는 이전 앞자리 수의 오르막 수 갯수를 모두 더한것과 같다.

위를 통해 규칙을 알아 낼 수 있다.

dp[i][j] = i자리수중 앞자리수가 j일때 오르막수의 갯수 라 정의하자.

dp[3][0] = 앞자리가 0인 3자리수의 오르막수 갯수

앞자리 수 0을 제외한 두번째 자리가 0으로 시작할때의 오르막수 갯수 = dp[2][0] 

앞자리 수 0을 제외한 두번째 자리가 1로 시작할때의 오르막수 갯수 = dp[2][1]

점화식은 dp[i][j] = dp[i][j] + dp[i-1][k] ( j <= k <= 9 )

위 규칙을 통해 코드로 구현했다.

import Foundation

let count = Int(readLine()!)!
var dp = Array(repeating: Array(repeating: 0, count: 10), count: count+1)
var result = 0

// 1자리 수는 오르막수도 1개
for i in 0..<10 {
    dp[1][i] = 1
}

// i자리 수에서 앞자리가 j일때 dp[i][j] += dp[i-1][k] ( j<= k <= 9 )
if count == 1 {
    result = dp[1].reduce(0 ,+)
} else {
    for i in 2...count {
        for j in 0...9 {
            for k in j...9 {
                dp[i][j] = (dp[i][j] + dp[i-1][k]) % 10007
            }
        }
    }
    result = dp[count].reduce(0, +) % 10007
}

print(result)

내가 푼 풀이

- 처음에는 dp[n] = max(dp[n-r] + 1, dp[n]) 의 방법으로 풀었다.

- 위 방법은 동전의 구성이 같고 순서만 달라도 다른경우로 취급했을 경우의 경우의수이다.

- 문제의 핵심은 k가치인 동전으로 k보다 가치가 낮게 만들 수 없다는것이다.

- 가치가 담긴 배열을 오름차순으로 정렬후, 낮은가치부터 dp에 저장한다

- dp[n]: n원을 만들 수 있는 경우의 수

동전가치의 배열: [1,2] , dp[k]: k원을 만드는 경우의 수

1,2 가치의 동전들로 0원을 만드는 경우의 수는 동전을 사용하지않는경우 1가지이다.

dp[0] = 1

n = 1 일때, dp[2] = dp[2] + dp[2 - 1] = 1

n= 2 일때, dp[2] = dp[2] + dp[2 - 2] = dp[2] + dp[0] = 2

점화식: dp[n] = dp[n] + dp[n-현재동전의가치] ( n >= 현재 동전의가치)

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var arr = [Int]()
var dp = Array(repeating: 0, count: inputs[1]+1)
for i in 0..<inputs[0] {
    arr.append(Int(readLine()!)!)
}
// 동전의 가치 오름차순으로 정렬
// 동전들로 0원을 만드는 경우의 수는 1가지 (동전을 쓰지않는방법)
arr.sort{ $0 < $1 }
dp[0] = 1

// k가치의 동전은 k보다 낮은가치를 만들 수 없다.
// 동전들마다 만들 수 있는 경우의 수를 dp에 저장한다.
// dp[n]: n원으로 만들 수 있는 경우의 수
for i in 0..<arr.count {
    for j in 0..<dp.count {
        if j-arr[i] >= 0 {
            if dp[j] + dp[j-arr[i]] >= Int(pow(2.0, 31.0)) {
                dp[j] = 0
            } else {
                dp[j] = dp[j] + dp[j-arr[i]]
            }
        }
    }
}

print(dp[inputs[1]])

문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

내가 푼 풀이

- 주어진 추와 같은 무게의 물건을 잴 수 있고, 추로 잴 수 없는 무게의 최솟값을 구한다.

- 추의 무게를 오름차순으로 정렬 후, 추가 추가 될때마다 잴 수 있는 무게들을 배열에 두었다.

- 배열의 최솟값과 최댓값이 연속된다면, 잴 수 없는 무게는 최댓값+1 이 되고, 연속되지 않는다면 끊어진 무게 중 최솟값을 출력했다.

- 결과는 시간초과가 떴다.

- 연산 시간을 줄일 방법이 떠오르지 않아서, 결국 다른 사람의 풀이를 참고했다.

- 추의 무게를 오름차순으로 정렬후, 한 개씩 추가해 가며 측정할 수 있는 범위를 갱신한다.

- 추를 추가했을때 측정범위와, 이전 측정범위가 연속되지 않는다면, 이전 측정범위의 최댓값 + 1 이 측정할 수 없는 무게의 최솟값이 된다.

- 추를 모두 추가했는데 연속된다면, 측정범위의 최댓값 + 1 이 최솟값이 된다.

- 오름차순으로 정렬된 추의 첫 번째 무게가 1보다 크면, 측정할 수 없는 무게의 최솟값은 1 이 된다.

도움을 받은 글: https://aerocode.net/392

예제입력을 통해 예시를 들어보자

무게배열: [3,1,6,2,7,30,1] 이 주어졌을 때

오름차순으로 정렬하면 [1,1,2,3,6,7,30]이다.

- 무게 1을 추가했을 때

• 이전 측정범위: [0, 0]
• 추가한 측정범위: [1, 1]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 2

- 무게 1을 추가했을 때

• 이전 측정범위: [0, 1] 
• 추가한 측정범위: [1, 2]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 3

- 무게 2를 추가했을 때

• 이전 측정범위: [0, 2] 
• 추가한 측정범위: [2, 4]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 5

- 무게 3을 추가했을 때

• 이전 측정범위: [0, 4] 
• 추가한 측정범위: [3, 7]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 8

- 무게 6을 추가했을 때

• 이전 측정범위: [0, 7] 
• 추가한 측정범위: [6, 13]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 14

- 무게 7을 추가했을 때

• 이전 측정범위: [0, 13] 
• 추가한 측정범위: [7, 20]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하므로 연속된다고 볼 수 있다.
• 측정할 수 없는 무게의 최솟값: 21

- 무게 30을 추가했을 때

• 이전 측정범위: [0, 20] 
• 추가한 측정범위: [30, 50]
• 이전 측정범위의 최댓값 + 1 >= 추가한 측정범위의 최솟값 이 성립하지 않는다.
• 이는 측정범위가 연속되지 않으므로 끊어진 범위중 최솟값을 구한다. [21,22,23,...,29] 중 최솟값
• 측정할 수 없는 무게의 최솟값: 21

따라서 주어진 추로 측정할 수 없는 무게의 최솟값은 21이 되는 것이다.

이를 바탕으로 코드로 구현한다.

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
var rangeNum = [0,0]
var min = 0
var sortedArr = arr.sorted{ $0 < $1}

// 추의 무게가 담긴 배열을 오름차순으로 정렬한다.
// 첫번째 추의 무게가 1보다 큰 수라면 최솟값은 1이된다.
// 첫번째 추의 무게가 1이고, 추의 갯수가 1 이라면 최솟값은 2가된다.
for i in 0..<sortedArr.count {
    if i == 0 {
        if sortedArr[i] != 1 {
            min = 1
        } else {
            rangeNum = [0,1]
            min = 2
        }
    } else {
        // range는 추가된 추로 새롭게 측정할 수 있는 범위
        // rangeNum은 이전의 추로 측정할 수 있는 범위이다.
        var range = rangeNum.map{ $0 + sortedArr[i]}
        
        
        // 이전의 측정가능한범위의 최댓값+1이 새롭게 측정가능한 범위의 최솟값 보다 크거나 같다면 연속된것
        // 연속됬다면 새롭게 측정가능한 범위의 최댓값+1이 정답이 된다.
        // 반대라면 끊어진 범위중 최솟값 출력
        if rangeNum[1]+1 >= range[0] {
            rangeNum = [0, range[1]]
            min = rangeNum[1] + 1
        } else {
            min = rangeNum[1] + 1
            break
        }
    }
    
}

print(min)

내가 푼 풀이

- 0과 1로 이루어진 행렬을 변환하는 연산은 3x3크기의 부분행렬의 모든원소를 뒤집는 것이다.

- 주어진 행렬이 연산이 불가능한 경우: N < 3 , M < 3

- 이 문제는 한 원소를 기준으로 3x3의 부분 원소를 변환했다.

- 행렬이 1행 1열 -> 1행 m열 -> n행 m열 순으로 인덱스를 접근한다면, 이미 접근한 인덱스는 연산이 이미 완료됐다고 본다.

- 인덱스로 접근할 때 행렬 A[n][m] 값과 B[n][m]값이 다르다면, n과 m기준으로 3x3의 부분행렬을 연산한다.

- n-2행 m-2열까지 모두 순회 후, 연산결과 출력

import Foundation

let inputs = readLine()!.split(separator: " ").map{ Int($0)! }
var a = [[String]]()
var b = [[String]]()
var result = 0

// 배열 입력받기
for i in 1...inputs[0]*2 {
    var arr = Array(readLine()!).map{ String($0) }
    if i <= inputs[0] {
        a.append(arr)
    } else {
        b.append(arr)
    }
}

// 배열의 크기가 연산가능한 크기보다 작다면
// 배열 a 와 b가 서로 다르다면, a는 b가 될 수 없으므로 -1
// 배열 a 와 b가 서로 같다면, a는 이미 b이므로 0 출력
if a.count < 3 || a[0].count < 3 {
    for i in 0..<a.count {
        let arr1 = a[i]
        let arr2 = b[i]
        if a[i] != b[i] {
            result = -1
        }
    }
    print(result)
} else {
    // 행은 n-2 까지, 열은 m-2 까지 순회
    // a[n][m] != b[n][m] 이면 연산
    for i in 0..<a.count-2 {
        for j in 0..<a[0].count-2 {
            var str1 = a[i][j]
            var str2 = b[i][j]

            if str1 == str2 {
                continue
            } else {
                result += 1
                for k in 0..<3 {
                    for n in 0..<3 {
                        if a[i+k][j+n] == "1" {
                            a[i+k][j+n] = "0"
                        } else {
                            a[i+k][j+n] = "1"
                        }
                    }
                }
            }
        }
    }
    
    // 연산결과 a와 b가 완전히 같은지 비교
    for i in 0..<a.count {
        let arr1 = a[i]
        let arr2 = b[i]
        
        if a[i] != b[i] {
            result = -1
        }
    }

    print(result)

}

문제

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

위의 그림의 경우에 점수가 50, 50, 100, 60인 스티커를 고르면, 점수는 260이 되고 이 것이 최대 점수이다. 가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.

내가 푼 풀이

- 해당 위치의 스티커를 붙이게 된다면, 위치 기준 양옆 위아래 붙일 수 없다.

- 해당 열에서 스티커를 붙이고, 그 다음 열에 스티커를 붙인다면 0행이라면 1행의 스티커를, 1행이라면 0행의 스티커를 붙일 수 있다.

- 해당 열에서 스티커를 붙이지 않는 경우, 같은 행의 이전 열에서 최댓값(dp)을 가져온다.

- 두가지 경우중 최댓값을 dp에 저장한다.

- dp를 스티커의 열의 개수+1 만큼 선언한다.

- dp[i][j]: i행 j열 위치까지의 스티커 점수 최댓값

스티커 점수 배열 arr //  dp[i][j]: i행 j열 위치까지의 스티커 점수 최댓값

• dp[0][1] = arr[0][1], dp[1][1] = arr[1][1]
• 0행 n열의 스티커를 붙이는 경우: dp[1][n-1] + arr[0][n]
• 0행 n열의 스티커를 붙이지 않는 경우: dp[0][n-1]
• 위 두 가지 경우 중 최댓값을 dp에 저장한다.
• dp[0][n] = max(dp[1][n-1] + arr[0][n], dp[0][n-1])
• dp[1][n] = max(dp[0][n-1] + arr[1][n], dp[1][n-1])
• 마지막 값 중 최댓값을 출력

import Foundation

let count = Int(readLine()!)!

// 2행 n열 스티커의 점수 입력받기
// dp의 인덱스 접근 편의상 맨 앞에 [0] 추가
// 해당 인덱스의 스티커를 붙이는 경우와 붙이지 않는경우 중 최댓값을 dp에 저장한다
for i in 0..<count {
    let size = Int(readLine()!)!
    var dp = Array(repeating: Array(repeating: 0, count: size+1), count: 2)
    var arr: [[Int]] = [[0] + readLine()!.split(separator: " ").map{ Int($0)! }] + [[0] + readLine()!.split(separator: " ").map{ Int($0)! }]

    dp[0][1] = arr[0][1]
    dp[1][1] = arr[1][1]
    if size == 1 {
        print(max(dp[0][size], dp[1][size]))
    } else {
        for j in 2...size {
            dp[0][j] = max(dp[1][j-1] + arr[0][j], dp[0][j-1])
            dp[1][j] = max(dp[0][j-1] + arr[1][j], dp[1][j-1])
        }
        print(max( dp[0][size], dp[1][size]))
    }
    
    
}