CodeDrive

문제:

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

입력:

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력:

격자의 밖으로 나간 모래의 양을 출력한다.

풀이방법:

 이 문제의 핵심은 회오리 모양으로 토네이도가 이동하는 것을 구현, 토네이도가 이동함에 따라 모래가 흩날리는 것을 구현해야 한다.

우선 회오리 모양으로 이동하는 것은 다음과 같은 규칙이 있다.

1) 방향은 좌, 하, 우, 상 을 반복하며 진행된다.

  - 따라서 dx, dy를 +1할 때마다 방향이 좌, 하, 우, 상으로 바뀌게 설정한다.

2) 좌, 하, 우, 상으로 이동할 때 거리는 1, 1, 2, 2, 3, 3, 4, 4, .... 와 같이 매 짝수 인덱스마다 증가하게 된다.

  - 다만 맨 마지막은 N-1, N-1, N, N, N 과 같이 N이 3번 반복되며 끝난다.

따라서 1), 2)의 조건을 만족하며 토네이도를 이동시키고, 토네이도가 0,0에 도달하면 이동을 종료하도록 한다. (소멸)

 모래가 흩날리는 것은 spread라는 배열을 만들어서 해결한다. 모래가 흩날리는 것은 좌, 하, 우, 상에 따라 흩날리는 위치가 다르기 때문에 방향 인덱스에 따라 모래의 이동 인덱스를 정리해둔다. 그리고 해당 인덱스에 따라 모래가 이동할 양인 ratio를 설정하도록 한다. 이 때, a의 경우에는 ratio를 0으로 설정한 뒤 따로 설정하도록 한다. 

 global 변수 answer를 설정하고, 범위 밖으로 나가는 모래는 다 answer에 더하고, 나머지는 지도에 계속 누적시키도록 한다.

이 두 기능을 계속해서 반복했을 때, 최종 answer를 출력한다.

문제링크:

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

문제:

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력:

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

출력:

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

풀이방법:

 시작점으로부터 드래곤 커브들의 방향을 구한 뒤에 모든 세대에 대한 점을 기록하는 방식으로 진행한다. 드래곤 커브를 만들 때 하나의 규칙은 N세대의 드래곤 커브를 만들기 위해 N-1세대의 끝 부터 시계 반대방향으로 90도를 회전시키면서 이어붙이면 처음부터 끝까지 한 배열에서 이어지게 만들 수 있다. 따라서 이전 세대의 끝부터 다음 세대를 진행시키도록 한다.

 모든 드래곤 커브를 그린 뒤에 100x100를 모두 탐색하며 각 꼭짓점이 모두 1인 경우만 +1을 해준다.

문제링크:

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

문제:

어른 상어가 마법사가 되었고, 파이어볼을 배웠다.

마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

입력:

첫째 줄에 N, M, K가 주어진다.

둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다.

서로 다른 두 파이어볼의 위치가 같은 경우는 입력으로 주어지지 않는다.

출력:

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 출력한다.

풀이방법:

 주어진 조건대로 구현을 수행하도록 한다. 한 칸에는 여러 개의 파이어볼이 존재할 수 있기 때문에 deque로 구성되어 있는 maps을 구성하도록 한다. 주어진 입력을 모두 정리한 뒤에 K번 이동을 시작한다.

 maps를 모두 탐색하면서 하나의 파이어볼이라도 있다면 이동 명령을 수행한다. 이 때, 벽을 만나더라도 1행-N행, 1열-N열은 모두 연결되어 있기 때문에 %명령어로 이를 해결하도록 한다.

 모든 파이어볼 이동이 끝난 뒤에 다시 한번 maps를 모두 탐색하도록 한다. 이번에는 파이어볼이 2개 이상 있는 칸을 탐색하며 해당 칸에 대해 합치고 분배되는 명령을 수행하도록 한다.

 두 명령을 K번 수행한 후, maps에 남은 파이어볼의 질량을 모두 합하도록 한다.

문제링크:

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

문제:

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력:

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

풀이방법:

DP를 사용해서 해당문제를 풀도록 한다. 이 때, N이 6번까지는 ctrl+A,C,V를 사용하는 것보다 하나를 더 추가하는 것이 더 이득이기 때문에 하나씩 추가하도록 한다. 복사 붙여넣기를 하기 위해서는 최소 3개의 명령어를 사용해야 한다. 따라서 ACV, ACVV, ACVVV, ...와 같은 방법으로 붙여넣기를 진행할 수 있다. 하지만 붙여넣기는 최대 3번만 사용해도 최댓값을 구할 수 있기 때문에 ACV, ACVV, ACVVV 와 같은 3개 경우에 대해서 DP를 진행하도록 한다.

점화식은 dp[i] = max(dp[i-3-j]*(2*j), dp[i])와 같다.

문제링크:

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

문제:

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력:

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

풀이방법:

 비트마스킹을 사용하여 해당 문제를 풀었다. N*M의 크기의 직사각형을 0,1의 비트마스킹으로 표현한다. 이 때 0은 가로로 연결되는 경우를 의미하고, 1은 세로로 연결되는 경우를 의미하게 된다.

 주어진 케이스에 대해 가로와 각각 따로 계산을 수행하도록 한다. 가로는 idx가 0인 경우에 대해서만 이어붙이며 값을 누적시키도록 한다. 반대로 세로는 idx가 1인 경우에 대해서만 이어붙이고 값을 누적시킨다. 모든 케이스에 대해서 이 작업을 반복 수행하며 가장 큰 경우를 출력하도록 한다.

문제링크:

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

문제:

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력:

첫째 줄에 세 정수 A, B, C가 주어진다.

출력:

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

풀이방법:

A, B를 담을 수 있는 물통들을 기준으로 하여 visited 배열을 만들고, BFS를 수행하도록 한다. visited의 가능한 갯수는 A와 B에 담을 수 있는 경우의 수와 같다. 처음은 비어있기 때문에, (0,0)으로부터 시작하도록 한다. 매 C는 가지고 있는 A, B 물의 양을 통해 구하도록 한다. 가지고 있는 A, B, C 물의 양을 통해 이동할 수 있는 모든 경우에 대해 조사하도록 한다. (A-> B, A-> C, B->C, B-> A, C-> A, C-> B)와 같은 총 6가지 case가 존재한다. 가능한 모든 경우에 대해 BFS를 수행하며 A의 물의 양이 0인 경우에 C의 값을 저장하도록 한다.

문제링크:

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

문제:

정수 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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 1,000,000보다 작거나 같다.

출력:

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

풀이방법:

 이전 1, 2, 3 더하기 문제에서는 재귀형태로 문제를 풀었지만 이번에는 숫자의 범위가 크기 때문에 시간초과가 발생할 것이다. 따라서 이번에는 dp 배열을 사용하여 문제를 풀도록 한다. 

 점화식은 간단한 편이다. N을 만들기 위해서 N-3의 경우에서 3을 N-2의 경우에서 2를 N-1일 대는 1을 각각 더해주면 되기 때문이다. 즉, dp[N] = dp[N-1] + dp[N-2] + dp[N-3]과 같다.

1000000까지 dp를 만든 뒤에 N 값을 출력하도록 한다.

문제링크:

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

문제:

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력:

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

풀이방법:

 처음에는 문제를 조금 이해하는 것이 어려웠다. 주어진 모든 사람의 관계가 조건과 같이 구성되어야 하는줄 알았는데, 일부 사람들만 관계를 유지하면 된다. 따라서 N명의 사람들의 관계를 트리 형태로 구성했을 때, 하나의 노드로부터 깊이가 4인 경우가 있는지 확인하면 된다.

 따라서 처음에는 주어진 관계들을 양방향 그래프로 정리를 한다. 그 다음에는 각 노드로부터 dfs를 수행했을 때, 깊이가 4인 경우가 있는지 확인한다. 깊이가 4인 경우가 한 개라도 있으면 되기 때문에 찾았다면 탐색을 중지하고 1을 출력하며, 모든 노드로부터 탐색했는데 없다면 0을 출력하도록 한다.

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

문제:

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력:

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

풀이방법:

 모든 케이스에 대해 수행하기에는 경우의 수가 너무 많기 때문에 그리디하게 이 문제를 해결하도록 한다. 각 알파벳에 대해 가중치를 구한 뒤에 가중치가 높은 순서대로 9부터 숫자를 할당하면 된다.

 가중치는 알파벳이 있는 위치, 갯수에 따라 다르게 설정한다. ABC와 같이 있을 때, 이를 숫자로 보면 A00, B0, C와 같다. 즉 자릿수가 클수록 더 높은 가중치를 가지게 된다. 따라서 word를 순회하면서 가중치를 순회하도록 한다. 이를 dict 형태로 저장하는데, 불필요한 키들을 줄이기 위해 defaultdict을 사용하여 깔끔하게 정리하도록 한다.

 최종적으로는 가중치에 따라 값을 부여하고 합을 누적시키도록 한다.

문제링크:

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

문제:

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 3개, 뺄셈(-) 2개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 250가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6
• 1+2+3+4-5-6
• 1+2+3-4-5×6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7
• 1+2+3+4-5-6 = -1
• 1+2+3-4-5×6 = -18

N개의 수와 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력:

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

풀이방법:

 처음에는 이 문제를 permutation을 사용해서 풀려고 했으나 시간초과나 메모리초과가 발생하게 되었다. 따라서 조금 더 효율적인 방법을 찾고자 고안한 방법은 백트래킹 방법이다.

 permutation은 매 candidate마다 값을 계산해야 한다. 하지만 1,1,3이라는 숫자가 있을 때, 1+1을 한번만 구한 뒤에 3에다가 추가적인 연산을 하는 것이 더 효율적이다. 따라서 dfs를 사용해서 백트래킹 방법을 사용하여 모든 케이스에 대해 연산을 수행하도록 한다. 

문제링크:

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