230816 - [Java-python] BruteForce 완전탐색 응용

[robert-min]

BOJ.14888 연산자 끼워넣기 링크

• 풀이과정
  • N, nums, operators 입력
  • 식이 완성되는 값을 누적하여 계산 후 최댓값, 최솟값 확인
  • 결과 출력

파이썬 풀이

import math
def calculate(op, ori_value, next_value):
    if op == 0:
        ori_value += next_value
    elif op == 1:
        ori_value -= next_value
    elif op == 2:
        ori_value *= next_value
    else:
        ori_value /= next_value
        ori_value = math.trunc(ori_value)
    return ori_value

def search(cand: int, value: int):
    global MIN_VALUE, MAX_VALUE
    # 종료 조건
    if cand == N:
        MAX_VALUE = max(MAX_VALUE, value)
        MIN_VALUE = min(MIN_VALUE, value)
    else:
        for i in range(4):
            if operators[i]:
                operators[i] -= 1
                search(cand+1, calculate(i, value, nums[cand]))
                operators[i] += 1

if __name__ == "__main__":
    # input
    N = int(input())
    nums = list(map(int, input().split()))
    operators = list(map(int, input().split()))

    # search
    import sys
    MAX_VALUE, MIN_VALUE = -sys.maxsize, sys.maxsize
    search(1, nums[0])

    # print
    print(MAX_VALUE)
    print(MIN_VALUE)

• 시간복잡도 최적화

  
  N = int(input())
  numbers = list(map(int, input().split()))
  flags = list(map(int, input().split())) # 덧셈, 뺄셈, 곱셈, 나눗셈 개수

import sys max_num = -sys.maxsize min_num = sys.maxsize

def dfs(depth, total, plus, minus, multiply, divide): """ parmas: numbers, flags = [덧셈, 뺄셈, 곱셈, 나눗셈] return: 식의 결과가 최대인것, 최소인 것 출력

1. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행

2. 나눗셈은 정수 나눗셈으로 몫 """ global max_num, min_num if depth == N: max_num = max(total, max_num) min_num = min(total, min_num) return

   if plus: dfs(depth+1, total + numbers[depth], plus-1, minus, multiply, divide) if minus: dfs(depth+1, total - numbers[depth], plus, minus-1, multiply, divide) if multiply: dfs(depth+1, total * numbers[depth], plus, minus, multiply -1 , divide) if divide: dfs(depth+1, int(total / numbers[depth]), plus, minus, multiply, divide - 1)

dfs(1, numbers[0], flags[0], flags[1], flags[2], flags[3]) print(max_num) print(min_num)

### java 풀이
```java

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, max, min;
    static int[] nums, operators;

    static void input() {
        N = scan.nextInt();
        nums = new int[N+1];
        operators = new int[5];
        for (int i = 1; i <= N; i++) nums[i] = scan.nextInt();
        for (int i = 1; i <= 4; i++) operators[i] = scan.nextInt();

        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;
    }

    // 선택된 operator와 값을 계산해주는 func
    static int calculator(int ori_num, int operator, int new_num) {
        if (operator == 1)
            return ori_num + new_num;
        else if (operator == 2)
            return ori_num - new_num;
        else if (operator == 3)
            return ori_num * new_num;
        else
            return ori_num / new_num;
    }

    // order[1..N-1에 연산자 순서대로 저장
    static void rec_fuc(int k, int value) {
        if (k == N) {
            // 완성된 결과 값 갱신
            max = Math.max(max, value);
            min = Math.min(min, value);
        } else {
            // 어떤 연산자 선택할지 결정
            for (int cand=1; cand <= 4; cand++) {
                if (operators[cand] >= 1) {
                    operators[cand]--;
                    rec_fuc(k+1, calculator(value, cand, nums[k+1]));
                    operators[cand]++;
                }
            }
        }

    }

    public static void main(String[] args) {
        // input
        input();

        // 1번째 부터 탐색 후 결과 order에 저장
        rec_fuc(1, nums[1]);

        // 출력
        sb.append(max).append("\n").append(min);
        System.out.println(sb.toString());

    }

}

[robert-min]

BOJ.9663 N-Queen 링크

• 문제 풀이
  • 위의 행부터 차례대로 퀸을 놓으면서 확인
  • 전체 graph를 그리지 않아도 값의 차이를 확인하면서 퀸 놓을 수 있는지 확인 가능

python 풀이

N = int(input())

graph = [0] * N
ans = 0

def check(x):
    for i in range(x):
        # 같은 열에 있거나 대각선에 있는 경우는 놓을 수 없음
        if graph[x] == graph[i] or abs(graph[x] - graph[i]) == abs(x - i):
            return False
    return True

def search(x):
    global ans
    if x == N:  # 마지막 행까지 탐색
        ans += 1
        return
    else:
        for i in range(N):  # 열 탐색
            # [x, i]에 퀸을 놓음
            graph[x] = i    # 매번 그래프를 새로 작성하지 않아도 됨.
            # 놓을 수 있는지 확인
            if check(x):
                # 놓을 수 있는 경우만 계속 탐색
                search(x+1)

search(0)
print(ans)

java 풀이

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static void input() {
        N = scan.nextInt();
        col = new int[N + 1];
    }

    static int N, ans;
    static int[] col;

    static boolean attackable(int r1, int c1, int r2, int c2) {
        if (c1 == c2) return true;
        if (r1 - c1 == r2 - c2) return true;
        if (r1 + c1 == r2 + c2) return true;
        return false;
    }

    static void rec_func(int row) {
        if (row == N + 1) {
            ans++;
        } else {
            for (int c = 1; c <= N; c++) {
                boolean possible = true;
                for (int i = 1; i <= row - 1; i++) {
                    if (attackable(row, c, i, col[i])) {
                        possible = false;
                        break;
                    }
                }
                if (possible) {
                    col[row] = c;
                    rec_func(row + 1);
                    col[row] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        input();
        // 1 번째 원소부터 M 번째 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
        rec_func(1);
        System.out.println(ans);
    }
}

[robert-min]

BOJ.1182 부분수열의 합 링크

• 문제풀이
  • backtracking

파이썬 풀이

def search(idx):
    global count
    if sum(answer) == S and len(answer) >0:
        count += 1

    for i in range(idx, N):
        answer.append(nums[i])

        search(i+1)
        answer.pop()

if __name__ == "__main__":
    # input
    N, S = map(int, input().split())
    nums = list(map(int, input().split()))
    answer = []
    count = 0
    # search
    search(0)

    # output    
    print(count)   

자바 풀이

import java.io.*;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int N, S, ans;
    static int[] nums;

    static void input() {
        N = scan.nextInt();
        S = scan.nextInt();
        nums = new int[N+1];
        for (int i=1; i <= N; i++) nums[i] = scan.nextInt();
    }

    static void rec_search(int k, int value) {
        if (k == N+1) {
            if (value == S) ans++;
        } else {
            // include
            rec_search(k+1, value+nums[k]);
            // Not include
            rec_search(k+1, value);
        }
    }

    public static void main(String[] args) {
        // input
        input();

        // search
        rec_search(1, 0);

        // check 진 부분집합 확인
        if (S == 0) {
            ans--;
        }

        // 출력
        System.out.println(ans);
    }
}

[robert-min]

조이스틱 링크

python 풀이

from itertools import permutations as p

INF = int(1e9)

# 알파벳이 주어졌을 때 상하로 움직이는 횟수 구하는 함수
def countChange(alp):
    return min(ord('Z') - ord(alp) + 1, ord(alp) - ord('A'))

# 왼쪽, 오른쪽 중 최단으로 가는 거리 구하는 함수
def findShortestPath(name, now, next):
    right, left = max(next, now), min(next, now)
    rightDist = right - left
    leftDist = left + len(name) - right
    return min(rightDist, leftDist)

def solution(name):
    answer = INF
    # "A" 가 아니라서 가야하는 위치(시작 위치 제외)
    toGoPlaces = [i for i in range(len(name)) if name[i] != "A" and i != 0]

    # 알파벳을 바꾸느라 생기는 이동
    changeCount = 0
    for c in name:
        changeCount += countChange(c);

    # 움직일 수 있는 모든 케이스
    cases = p(toGoPlaces, len(toGoPlaces))
    for case in cases:
        now = 0
        result = 0

        for next in case:
            dist = findShortestPath(name, now, next)
            result += dist
            now = next

        answer = min(answer, result + changeCount)
    return answer