그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 선분을 이용하여 그래프를 구성한다.

   • 두 선분이 친구 관계라면 1, 친구 관계까 아니라면 아주 큰 값(INT_MAX)으로 설정
   • 두 선분이 친구 관계인지 확인하려면 총 세가지 케이스를 확인해야 한다.
     1. 하나의 선분의 왼쪽 끝이 다른 선분 안에 있거나, (왼쪽은 겹치고 오른쪽은 선분 밖에)
     2. 오른쪽 끝이 다른 선분 안에 있거나. (오른쪽은 겹치고 왼쪽은 선분 밖에)
     3. 하나의 선분의 왼쪽 끝이 다른 선분보다 작고, 오른쪽 끝이 다른 선분보다 클 때(덮을 때)
     4. 아예 안에 들어있을 때는 (1), (2)에 걸리므로 따로 처리할 필요 없음

2. Floyd 알고리즘을 사용하여 각 선분에서 다른 선분으로 이동 가능한 최단 거리를 테이블로 미리 구성해 둔다.

   • 삼중 반복문을 통해 거쳐가는 모든 케이스 조사
   • 반복문 순서가 중요함!! 맨 바깥쪽 반복문이 거쳐가는 노드
     • distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
     • k가 거쳐가는 노드
   • T의 최대가 300이라서.. 300 * 300 * 300을 해야되는데 좀 크지 않나라고 생각했지만 잘 된다. 생각해보니 후에 Q개의 줄에 걸쳐 최단경로를 입력받고 출력해야되서 좀 오래걸리더라도 다 구해둬야 되는게 맞음.

3. 입력받은 두 선분 사이의 거리를 출력해 준다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

T = int(input())
lines = [list(map(int, input().split())) for _ in range(T)]
INT_MAX = int(10e9)
graph = [[INT_MAX] * T for _ in range(T)]

for i in range(len(lines)):
    for j in range(i+1, len(lines)):
        if (lines[i][0] <= lines[j][0] and lines[j][0] <= lines[i][1]) or \
        (lines[i][0] <= lines[j][1] and lines[j][1] <= lines[i][1]) or \
        (lines[j][0] <= lines[i][0] and lines[j][1] >= lines[i][1]):
            graph[i][j] = 1
            graph[j][i] = 1

for i in range(T):
    for j in range(T):
        for k in range(T):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

Q = int(input())
for _ in range(Q):
    src, dest = map(int, input().split())
    src, dest = src - 1, dest - 1

    if graph[src][dest] == INT_MAX:
        print(-1)
    else:
        print(graph[src][dest])

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

풀이과정

1. 맨 왼쪽부터 X개의 합계를 먼저 구해두고 시작.

2. [i ~ i+X]의 합계중 최댓값을 구하면 되는 문제

   • 매번 합계를 구해주면 시간이 너무 오래 걸린다.
   • 따라서, [i ~ i+X]의 합계를 구한 다음, 다음 구간의 합계에서는 [i]를 빼주고, [i+X+1]을 더해주면 그게 [i+1 ~ i+X+1]의 합계이다.
   • 이러한 방식으로 진행하면서 합계중 최댓값을 저장해두고, 최댓값이 같은 경우 최댓값의 개수도 같이 증가

3. 최댓값과 최댓값의 갯수를 출력해 준다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()
N, X = map(int, input().split())
log = list(map(int, input().split()))

max_visitor = 0
max_visitor_cnt = 0

visitor = sum(log[:X])
left = 0
right = X-1

while right < N:
    if max_visitor < visitor:
        max_visitor = visitor
        max_visitor_cnt = 1
    elif max_visitor == visitor:
        max_visitor_cnt += 1

    if right == N-1:
        break

    visitor -= log[left]
    left += 1
    right += 1
    visitor += log[right]

if max_visitor == 0:
    print("SAD")
else:
    print(max_visitor)
    print(max_visitor_cnt)

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

풀이 과정

1. 가장 큰 수를 만들려면 1, 7만으로 최대한 자리수를 늘리기만 하면 된다. (각각 2개, 3개이며 나머지는 4개 이상이므로 1 두개 넣는것보다 작음)

   • 성냥개비 개수가 홀수라면 맨앞에 7을 넣어주고 나머지는 1, 짝수라면 전체 1만으로 구성

2. BFS를 사용하여 DP 테이블을 채워준다.

   • 최대 100개의 성냥개비를 사용 가능하므로 100개까지 진행
   • DP[i]는 i개의 성냥개비로 만들 수 있는 수의 최솟값
   • 큐에 들어가는 형식은 [성냥개비 수, 만들어진 수]
   • 맨 앞자리는 0이 들어갈 수 없으므로, 초기 큐에는 1~9까지만 넣어준다.
   • 매 단계 큐에 넣을때마다 뒤에 09를 붙여주고, 09를 만드는데 필요한 성냥 수를 더해서 넘겨준다.
     • 성냥 수가 100개를 넘어가면 안됨.
   • 큐에서 빼낼 때, 만들어진 수가 기존 수보다 작을때만 뒤에 붙여주는 과정 진행

3. 최솟값, 최댓값 형식으로 출력시켜주면 된다.

• 최솟값이 굉장히 큰 수가 나올 수 있으므로 초기 값 설정을 잘 해주어야 함. 초깃값을 10e9로 했다가 처음엔 틀렸는데, sys.maxsize로 바꾸어주니 정답이 나옴.

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip())

INT_MAX = int(sys.maxsize)

dp_max = [0] * 101
dp_min = [INT_MAX] * 101

count = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
initial = [[value, idx] for idx, value in enumerate(count)][1:]

queue = deque(initial)

while queue:
    cnt, make = queue.popleft()
    dp_min[cnt] = min(dp_min[cnt], make)
    if dp_min[cnt] != make:
        continue
    for i in range(10):
        if cnt + count[i] <= 100:
            queue.append([cnt + count[i], int(str(make)+str(i))])

for _ in range(T):
    p = int(sys.stdin.readline().rstrip())
    max_string = ''
    if p % 2 == 1:
        max_string = '7' + '1' * ((p-3) // 2)
    else:
        max_string = '1' * (p // 2)
    print(dp_min[p], max_string)

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

풀이 과정

1. 결국 1의 개수가 연속으로 딱 K개가 될 때중 하나가 가장 작은 연속된 인형들의 집합이다.
   • 따라서, 1의 위치들만 저장해둔 리스트들을 따로 만들어 둔다.
2. 1의 개수가 K개도 안된다면 애초에 불가능한 것이므로 -1 출력후 종료
3. 맨 앞에서부터 K개를 선택한다. => left는 0, right는 K-1이다.
   • 이 때, 인형의 개수는 리스트[right] - 리스트[left] + 1이므로, 이 값으로 최소 인형의 개수를 갱신해 준다.
   • 이후 한칸 옮겨서 left = left + 1, right = right + 1 해준다.
   • right가 배열의 끝까지 가게 되면 종료시켜 준다.
4. 최소 인형의 개수를 출력해 준다.

• 초기에는 막코딩 했는데 소스가 너무 지저분하고 이해하기 어려워서 맞았으나 다시 짬..

import sys

input = lambda :sys.stdin.readline().rstrip()

N, K = map(int, input().split())
dolls = list(map(int, input().split()))
answer = int(10e9)

lion_pos = []
for i in range(len(dolls)):
    if dolls[i] == 1:
        lion_pos.append(i)

left = 0
right = K-1

if len(lion_pos) < K:
    print(-1)
else:
    while right < len(lion_pos):
        answer = min(answer, lion_pos[right] - lion_pos[left] + 1)
        left, right = left+1, right+1
    print(answer)

이전 소스

• K개 맞추어 줄려고 매순간 값 갱신 이후에 left 1 증가시키고 lion 1 빼줌

import sys

input = lambda :sys.stdin.readline().rstrip()

N, K = map(int, input().split())

dolls = list(map(int, input().split()))


answer = int(10e9)

left = 0
right = 0
lion = 1 if dolls[0] == 1 else 0
while True:
    while right < len(dolls)-1 and lion < K:
        right += 1
        lion = lion + 1 if dolls[right] == 1 else lion

    while left < right and lion >= K:
        if dolls[left] == 1:
            if lion == K:
                break
            else:
                lion -= 1
        left += 1

    if lion >= K:
        answer = min(answer, right-left+1)

    left += 1
    lion -= 1

    if right == len(dolls)-1:
        break

if answer == int(10e9):
    print(-1)
else:
    print(answer)

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

풀이 과정

1. 일단 가장 왼쪽 초밥에서부터 연속해서 k개를 선택한다.

   • 이 때, 중복이 있을수 있으므로 초밥의 종류는 set에 저장하고 초밥의 개수는 딕셔너리에 저장한다.

2. 이제 왼쪽에서 한칸, 오른쪽으로 한칸 이동할 것이다.

   • 이전까지의 초밥의 종류가 0부터 k-1이라 하면 다음 초밥의 종류는 1부터 k, ...
   • left와 right를 1씩 증가하면서 배열의 크기를 넘어서는 경우가 있음
     • left = (left + 1) % 배열크기, right = (right+1) % 배열크기
   • 갱신하면서 왼쪽 딕셔너리의 값은 이동 전 1 감소시키고, 오른쪽 딕셔너리의 값은 이동 후 1 증가시킨다.
   • 딕셔너리의 값이 0이 되었다면 set에서 제거하고, 1이 되었다면 set에 추가한다.
   • 초밥의 최대 가짓수를 갱신해 주는데, 이 때 쿠폰 번호가 현재 초밥 종류에 속해 있다면 쓸수 없으므로 그대로, 속해있지 않다면 쓸수 있는 것이므로 1 더한 값으로 비교해 준다.

3. 왼쪽이 배열의 맨 마지막에 도달할때 까지 진행해 준다.

4. 초밥의 최대 가짓수를 출력해 준다.

소스 코드

import sys
from collections import defaultdict

input = lambda :sys.stdin.readline().rstrip()

N, d, k, c = map(int, input().split())
sushi = [int(input()) for _ in range(N)]
case = set()
case_count = defaultdict(int)
answer = 0

left = 0
right = k-1

for i in range(k):
    case.add(sushi[i])
    case_count[sushi[i]] += 1

total_case = len(case)+1 if c not in case else len(case)
answer = max(answer, total_case)


for i in range(N):
    case_count[sushi[left]] -= 1
    if case_count[sushi[left]] == 0: case.remove(sushi[left])
    left = (left + 1) % N

    right = (right + 1) % N
    if sushi[right] not in case: case.add(sushi[right])
    case_count[sushi[right]] += 1

    total_case = len(case)+1 if c not in case else len(case)
    answer = max(answer, total_case)

print(answer)

문제 설명

문제

게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.

예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.

    if power <= 10000 
        print WEAK 
    else if power <= 100000 
        print NORMAL 
    else if power <= 1000000 
        print STRONG

혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.

입력

첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M≤ 105)

두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다.

N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

출력

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

풀이 과정

1. 입력받은 칭호와 전투력을 딕셔너리 형태로 저장, 전투력만 따로 리스트에 저장

   • dict[전투력] = 칭호 형식

2. 칭호 전투력 리스트를 정렬

   • 이분탐색을 하기 위함

3. 칭호 전투력 리스트에 대해 이분탐색 진행

   • 리스트의 중간값이 입력받은 값보다 크면 왼쪽 구간 진행
   • 리스트의 중간값이 입력받은 값보다 작으면 오른쪽 구간 진행
   • 단, 여기서 왼쪽 구간 진행할 때는 최댓값을 구해야 하므로 현재 중간값을 저장해 두어야 한다.

4. 입력받은 중간값에 대응하는 칭호 출력

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()

N, M = map(int, input().split())

types = {}

def bisect(value, arr):
    left = 0
    right = len(arr)-1
    target = 0
    while left <= right:
        mid = (left + right) // 2

        if arr[mid] >= value:
            target = mid
            right = mid - 1
        else:
            left = mid + 1

    return target

values = []
for _ in range(N):
    name, value = input().split()
    value = int(value)
    if types.get(value) == None:
        types[value] = name
        values.append(int(value))

values.sort()
for _ in range(M):
    value = int(input())
    pos = bisect(value, values)
    print(types[values[pos]])

문제 설명

문제

N개의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면,

색칠된 부분의 곱이 최대가 되며, 그 값은 1.638이다.

입력

첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 같고, 9.9보다 작거나 같다.

출력

계산된 최댓값을 소수점 이하 넷째 자리에서 반올림하여 소수점 이하 셋째 자리까지 출력한다.

풀이 과정

1. 현재 위치를 i라고 할 때, i에 올수 있는 경우는 두가지이다.

   • 이전까지의 곱에 i를 곱하는 경우
   • i에서 시작하는 경우

2. 따라서, 두가지 경우중 최댓값을 dp[i]로 설정해주면 된다.

3. 마지막으로, 출력 형식을 잘 보아야 함.

   • 4번째 자리에서 반올림 시킨후 소수점 셋째자리까지 출력해주어야 함.
   • 1 (x) 1.000 (o)

소스 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
numbers = [float(input().rstrip()) for _ in range(N)]
dp = [0] * N

dp[0] = numbers[0]

for i in range(N):
    if i > 0:
        dp[i] = max(dp[i-1] * numbers[i], numbers[i])

print("%.3f"%(round(max(dp), 3)))

문제 설명

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 또, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 수를 제거하지 않았을 때의 정답은 12+21인 33이 정답이 된다.

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이 과정

1. DP를 진행한다.
   • 수열에서 수를 하나 제거할 수 있으므로
   • DP[i][0]: 수를 제거하지 않은 경우
   • DP[i][1]은 수를 제거한 경우
2. 현재 선택한 수열의 인덱스를 i라고 두고, 입력받은 정수 배열명을 temp라고 할 때
   • 수를 제거하지 않은 경우에는 두가지 케이스가 올 수 있다.
     1. 이전 합계를 끌고와서 자기 숫자를 더해주는 경우
        => dp[i][0] = dp[i-1][0] + temp[i]
     2. 이전 합계가 음수여서 자기 자신에서 시작하는 경우
        => dp[i][0] = temp[i]
     3. 둘중 최댓값을 dp[i][0]에 대입해준다.
   • 수를 제거한 경우에는 두가지 케이스가 올 수 있다.
     4. 자기 숫자를 제거하는 경우
        => dp[i][1] = dp[i-1]
     5. 이전에 이미 숫자가 제거된 경우
        => dp[i][1] = dp[i-1] + temp[i]
     6. 둘중 최댓값을 dp[i][0]에 대입해준다.
3. 전체 테이블에 대한 최대값을 구하면 된다.
   • 단, n이 1일 때는 무조건 선택해야 하므로 입력받은 수를 바로 리턴해주면 된다.

소스 코드

N = int(input())
temp = list(map(int, input().split()))

dp = [[0, 0] for _ in range(N)]
dp[0][0], dp[0][1] = temp[0], 0


m = -int(10e9)
for i in range(1, N):
    dp[i][0] = max(temp[i], dp[i-1][0] + temp[i])
    dp[i][1] = max(dp[i-1][0], dp[i-1][1] + temp[i])

if N == 1:
    print(temp[0])
else:
    for i in range(1, N):
        m = max(m, dp[i][0], dp[i][1])
    m = max(m, dp[0][0])
    print(m)

문제 설명

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-99, -2, -1, 4, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액의 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 서로 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

풀이 과정

1. 초기 위치를 left는 0, right는 N-1로 둔다.
   • 가장 산성인 용액과, 가장 알칼리성 용액을 가리키도록 함.
2. 만약 현재 left, right가 가리키는 용액의 혼합 특성값이 0보다 크다면
   • right를 1 줄여줌. (알칼리성 용액의 농도를 낮추어야 0에 가까워진다.)
3. 만약 현재 left, right가 가리키는 용액의 혼합 특성값이 0보다 작다면
   • left를 1 늘려줌. (산성 용액의 농도를 낮추어야 0에 가까워진다.)
4. 과정을 진행하면서, 특성값의 합이 가장 낮을 때의 두 용액의 특성값을 저장해 둔다.

소스 코드

N = int(input())
ph = list(map(int, input().split()))

left = 0
right = N-1

min_ph = int(10e9)
value1, value2 = 0, 0

while left < right:
    if abs(ph[left] + ph[right]) <= min_ph:
        min_ph = abs(ph[left] + ph[right])
        value1 = ph[left]
        value2 = ph[right]

    if ph[left] + ph[right] > 0:
        right -= 1
    else:
        left += 1

print(value1, value2)

문제 설명

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

이를 사전순으로 정렬하면 다음과 같이 된다.

1. 1+1+1+1
2. 1+1+2
3. 1+2+1
4. 1+3
5. 2+1+1
6. 2+2
7. 3+1

정수 n과 k가 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법 중에서 k번째로 오는 식을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n과 k가 주어진다. n은 양수이며 11보다 작고, k는 231-1보다 작거나 같은 자연수이다.

출력

n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다.

풀이 과정

1. 사전순으로 정렬된 리스트를 얻어야 하므로, Recursion으로 구현 할 때 현재 합에서 1->2->3 순으로 더하도록 Recursion을 진행한다.
2. Recursion을 진행한다.
   • 현재 사용한 숫자들에 1, 2, 3을 넣고, 사용한 숫자를 합계에 더해서 다음 Recursion 호출
   • Recursion을 진행하다 현재 합계가 n보다 커진다면 종료
   • n과 같다면 리스트에 추가하고 종료한다.
3. 2번 과정을 진행하면 결국 1,2,3의 합으로 나타내는 모든 방법이 정렬되어 있는 리스트를 얻게 된다.
   • 따라서, k-1번째 인덱스의 방법을 출력해주면 된다.
   • 이 때, k-1이 방법의 수보다 큰 경우가 있으므로, 이 때는 -1을 출력해준다.

소스 코드

n, k = map(int, input().split())

case = []
def dfs(numbers, sumation, target):
    global case

    if sumation == target:
        case.append(numbers)
        return
    if sumation > target:
        return

    for i in [1, 2, 3]:
        dfs(numbers + [i], sumation + i, target)

dfs([], 0, n)
if k - 1 < len(case):
    print("+".join(map(str, case[k-1])))
else:
    print(-1)