삼성 SW 역량 테스트, 코딩 테스트 문제로
백준 온라인 저지에 올라와있는 14888번 연산자 끼워넣기 문제를 풀어봅시다.
역량 테스트 문제에 브루트 포스 문제가 많은 것 같은데요
이 문제도 브루투 포스 즉, 완전 탐색을 하면 풀 수 있는 문제에요
직접 풀어 보고 싶으신 분들은 아래 링크로 들어가서 풀어보세요!!
https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
www.acmicpc.net
예제 입출력을 보고서 문제를 이해하는게 제일 빠른것 같아요
간단히 문제먼저 이야기 하자면 연산자와 숫자가 주어지면 결과로 나올 수 있는 값들이
여러가지가 존재하겠죠???? 그대신 주어진 수의 순서는 그대로기 때문에 경우의 수는 훨씬 적어져요
예를들어 1,2,3가 있고 연산자로 +, -가 있다면
이렇게 두 가지 경우가 가능해요
이때 가능한 값들 중에서 최소값가 최대값을 뽑아내면 되요!!
예제 입력과 출력
// 입력
3
3 4 5
1 0 1 0
// 출력
35
17
입력 첫 째줄은 피연산자의 개수에요. 즉 숫자들이죠 0부터 9까지의 숫자들!!
두번째 줄에 계산할 숫자들을 써주면 되요
그 다음 밑에줄에는 연산자들의 개수. 더하기, 빼기, 곱하기, 나누기 순서니까
더하기 1개, 곱하기 1개가 있다는 뜻이에요
그러면 총 나올 수 있는 경우는 아래와 같을 거에요. 총 2가지
피연산자 순서는 고정이기 때문에 연산자만 바꿔주면 되요
1. 3+4*5
2. 3*4+5
1번의 결과는 35. 이 때 왜 35냐면 우선 순위 없이 앞에서 부터 계산하기 때문이에요. 3과 4를 더하고 그렇게 해서 나온 7을 5에 곱하면 35!!
2번의 결과는 17
이제 문제는 이해가 되셨나요??
이번 문제도 역시 브루트 포스, 백트레킹을 이용해서 조합을 구했어요
combination 함수를 통해서 조합을 구하고 solve 함수, calculation함수를 통해서 답을 구해주었어요
계산을 편히 하기 위해서 +, -, *, / 를 0,1,2,3으로 대치해서 풀었어요
나누기(/)인 경우는 음수 나누기의 경우를 문제대로 예외처리를 해주었어요
자세한 내용은 아래 코드를 참고하세요!!
백준 14888번 연산자 넣기
자바 풀이
브루트 포스 방법으로 모든 경우를 계산해서 arraylist에 넣고 Collections 프레임워크를 이용해서
최소값과 최대값을 구했어요
코드를 보고 의문점이 들거나 더 좋은 방법이 있다면 공유해주세요!!
잘 보셨다면 하트 꾸욱 부탁드립니다!!
2019/10/13 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 브루트 포스, 순열] 삼성 SW 역량 테스트 문제 :: 14888번 연산자 끼워넣기
2019/10/11 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 브루트 포스] 삼성 SW 역량 테스트 문제 :: 14889번 스타트와 링크
2019/10/11 - [알고리즘/백준 알고리즘] - [백준 알고리즘, 브루트 포스] 삼성 코딩 테스트 문제 :: 13458번 시험감독 자바 풀이