백준-완탐 연습(Brute-Force)

쉬는 날이기에 근 1~2주 동안 일찍 출근해서 풀었던 문제와 못 푼 문제에 대해 정리해보고자 한다.
물론 다시풀어보면서 작성해보고자 한다.

1. 백준 일곱 난쟁이 [2309]

아홉 개의 숫자를 주고 그중에서 일곱 난쟁이를 찾는 문제이다. 이중 일곱 난쟁이의 키의 합은 100이라는 전제조건이 붙으며 정답이 여러 개 존재할 경우 아무거나 하나출력하면 된다.

func solution() {
	reader := bufio.NewReader(os.Stdin)

	arr := make([]int, 9)
	for i := range arr {
		var a int
		fmt.Fscanln(reader, &a)
		arr[i] = a
	}

	sort.Ints(arr)
	btc := func(arr, rs []int, idx, sum int) {}

	btc = func(arr, rs []int, idx, sum int) {
		if len(rs) > 7 || sum >= 100 || idx >= len(arr) {
			if sum == 100 {
				for _, v := range rs {
					fmt.Println(v)
				}
				os.Exit(0)
			}
		} else {
			btc(arr, append(rs, arr[idx]), idx+1, sum+arr[idx])
			btc(arr, rs, idx+1, sum)
		}
	}

	btc(arr, []int{}, 0, 0)
}

백트리킹 방식을 사용했다. 난쟁이를 선택한 경우와 그렇지 않은 경우

최초 정렬을 수행하고 다음 항목을 진행하는데 정답의 출력이 오름차순 출력이기에 최초 입력값 자체를 정렬해 주었다.

 

이 방법 외에도 간단하게 이중 포문을 돌려서 하나씩 제거하는 방법도 존재한다.

func solution() {
	reader := bufio.NewReader(os.Stdin)

	arr := make([]int, 9)
	var (
		total, x, y int
	)
	for i := range arr {
		var a int
		fmt.Fscanln(reader, &a)
		arr[i] = a
		total += a
	}

	sort.Ints(arr)
Loop:
	for i := 0; i < len(arr); i++ {
		for j := i + 1; j < len(arr); j++ {
			if total-(arr[i]+arr[j]) == 100 {
				x, y = i, j
				break Loop
			}
		}
	}

	for i := range arr {
		if i != x && i != y {
			fmt.Println(arr[i])
		}
	}
}

이렇게 수를 받아오면서 전체 수의 값을 계산하고 이중포문으로 하나씩 날려주면 된다. 

 

2. 백준 로또 [6603]
1~49의 숫자 중 6개를 고르는 것이다 단 집합 S를 만들고 해당 수의 번호만 선택하는 전략을 가져간다.

해당 부분집합은 총 6~13 개의 숫자로 되어있으며, 입력마지막 줄에는 0이 하나 주어진다.

 

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main() {
	solution()
}

func solution() {
	reader := bufio.NewReader(os.Stdin)
	answer := strings.Builder{}

	bitmask := func(arr, rs []string, flag, start int) {}
	bitmask = func(arr, rs []string, flag, start int) {
		if len(rs) >= 6 {
			ans := ""
			for _, v := range rs {
				ans += v + " "
			}
			answer.WriteString(ans + "\n")
			return
		} else {
			for i := start; i < len(arr); i++ {
				if flag&(1<<i) != 0 {
					continue
				}
				bitmask(arr, append(rs, arr[i]), flag|(1<<i), i+1)
			}
		}
	}

	for {
		line, _ := reader.ReadString('\n')
		if line[0] == '0' {
			break
		}
		input := strings.TrimSpace(line)
		target := strings.Split(input, " ")[1:]
		var rs []string
		bitmask(target, rs, 0, 0)
	}
	fmt.Println(answer.String())
}

해당 문제는 비트마스크를 이용해 해결했다. 여기서 비트마스크는 & | 연산을 활용하는 방법이다. 

최초 0의 플래그를 가지고 이동하며 플래그 즉 이진수의 각 자릿수는 배열의 방문을 표기한다. 

 

예를 들어 0의 플래그가 있고 최초방문 0의 자리를 방문한다고 했을 때 0 | (1<<0) 1을 0만큼 쉬프트 한다.  즉 1과 0을 or 연산을 하게 되고플 래그는 0000001의 값을 가진다. 이룰 활용한 방법이다. 

나의 맥북은 64비트 메모리를 사용하고 있으니 int는 int64 고되고 이는 총 64개의 방문배열을 처리할 수 있음을 의미하니 마음 놓고 사용해도 된다.

 

지난번도 그렇고 이번에 다시 풀 때도 그렇고 input을 읽어올 때 "\n" 읽어오고 trimspace를 안 해 자꾸 출력값이 이상해서 오답을 받았다.

ㅎㅎ....

 

3. 부분수열의 합 [1182]

총 20 개의 숫자와 하나의 숫자가 주어지고 몇몇의 숫자들을 선택해 합을 구해 주어진 하나의 숫자와 같은 경우의 개수를 출력해야 한다.

여기서 부분수열의 합이라서 연속된 배열의 부분수열의 합이라고 생각할 수 있다. 그게 아닌 특정 숫자들을 선택해 더하는 것이다.

func solution() {
	reader := bufio.NewReader(os.Stdin)

	var (
		n, answer, sum int
	)

	fmt.Fscanln(reader, &n, &sum)

	arr := make([]int, n)
	for i := range arr {
		var a int
		fmt.Fscan(reader, &a)
		arr[i] = a
	}

	find := func(arr []int, total, idx, flag int) {}
	find = func(arr []int, total, idx, flag int) {
		if idx >= len(arr) {
			if total == sum && flag > 0 {
				answer++
			}
			return
		} else {
			find(arr, total+arr[idx], idx+1, flag|(1<<idx))
			find(arr, total, idx+1, flag)
		}

	}
	find(arr, 0, 0, 0)
	fmt.Println(answer)
}

1번 백설공주  와 마찬가지로 숫자를 선택 혹은 넘기는 쪽을 선택했다. flag를 넣어준 이유는 총합이 0 이 되는 경우 answer는 0으로 초기화되기 때문에 최소 고른 횟수를 넣어주기 위해 위와 같이 넣어주었다.

 

4. 차이를 최대로 [10819] 

범위 또한 3~8로 순열 완탐에 최적화된 전형적인 순열 문제이다. 각 배열을 바꿔서 차이를 최대로 만들면 되기 때문에 순열을 이용해서 재배치 후 계산을 해주면 된다. 

func solution() {
	reader := bufio.NewReader(os.Stdin)
	abs := func(a int) int {
		if a < 0 {
			return -a
		}
		return a
	}
	cal := func(arr []int) (total int) {
		for i := 1; i < len(arr); i++ {
			total += abs(arr[i] - arr[i-1])
		}
		return total
	}

	var (
		n, answer int
	)

	fmt.Fscanln(reader, &n)

	arr := make([]int, n)
	for i := range arr {
		var a int
		fmt.Fscan(reader, &a)
		arr[i] = a
	}
	answer = cal(arr)

	recur := func(arr, rs []int, depth, flag int) {}
	recur = func(arr, rs []int, depth, flag int) {
		if depth >= len(arr) {
			sum := cal(rs)
			if answer < sum {
				answer = sum
			}
			return
		} else {
			for i := 0; i < len(arr); i++ {
				if flag&(1<<i) == 0 {
					recur(arr, append(rs, arr[i]), depth+1, flag|(1<<i))
				}
			}
		}
	}
	recur(arr, []int{}, 0, 0)
	fmt.Println(answer)
}

단순히 비트마스크를 이용해서 순열을 조회해서 다음으로 넘겨준다. 이게 전부다.

 

5. 스도쿠 [2580] 

예전에 풀어봤던 문제이다. 확실히 한번 풀어봐서인지 나름 손쉽게 풀 수 있었다.
(https://guiwoo.tistory.com/3 - 자바풀이)

백트리킹의 조건과 패스 될 수 있는 수의 경우만 명확하게 해 주면 된다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	solution()
}

func solution() {
	reader := bufio.NewReader(os.Stdin)
	arr := make([][]int, 9)
	for i := range arr {
		sub := make([]int, 9)
		for j := range sub {
			var a int
			fmt.Fscan(reader, &a)
			sub[j] = a
		}
		arr[i] = sub
	}
	isPossible := func(arr [][]int, num, row, col int) bool {
		//가로줄 체크
		for i := 0; i < 9; i++ {
			if arr[row][i] == num {
				return false
			}
		}

		//세로줄 체크
		for i := 0; i < 9; i++ {
			if arr[i][col] == num {
				return false
			}
		}

		// 3*3 체크
		row = (row / 3) * 3
		col = (col / 3) * 3
		for i := row; i < row+3; i++ {
			for j := col; j < col+3; j++ {
				if arr[i][j] == num {
					return false
				}
			}
		}
		return true
	}

	dfs := func(arr [][]int, cal int) {}
	dfs = func(arr [][]int, cal int) {
		if cal >= 81 {
			for i := range arr {
				for j := range arr[i] {
					fmt.Printf("%d ", arr[i][j])
				}
				fmt.Println()
			}
			os.Exit(0)
		}
		row := cal / 9
		col := cal % 9
		if arr[row][col] != 0 {
			dfs(arr, cal+1)
		} else {
			for i := 1; i <= 9; i++ {
				if isPossible(arr, i, row, col) {
					arr[row][col] = i
					dfs(arr, cal+1)
					arr[row][col] = 0
				}
			}
		}
	}
	dfs(arr, 0)
}

이문제는 row, col을 하나의 숫자로 넘겨서 계산해 주는 게 보다 손쉽게 계산할 수 있다. 

 

6. 단어나누기 [1251]

알파벳 소문자 가 주어지고 단어를 임의의 두 부분을 골라서 단어를 쪼개고 나눠진 단어들을 뒤집어서 다시 재조합해 사전에서 찾을 수 있는 가장 앞에 단어를 출력해야 한다.

단 나눠진 단어의 길이는 1 이상인 단어여야만 한다.

 

포인트는 임의의 두 부분을 골라서 단어를 나눈다는 것이다.

바로 슬라이스를 사용하면 된다. 예를 들어보자 "abcdefg"와 같은 단어가 있다면? 

func Test_StringSplit(t *testing.T) {
	a := "abcdefg"
	fmt.Println(a[:1]) // a
	fmt.Println(a[1:3]) // bc
	fmt.Println(a[3:]) // defg
	fmt.Println(a[7:]) // 
}

 

단어의 특정 부분을 고르는 것이 아닌 모든 부분을 사용해야 하기 때문에 딱 2개의 숫자만 고르면 된다. 단 길이가 7이라면 6까지 골라야 한다. 위에서 언급한 나눠진 단어는 길이가 최소 1 이상이어야 하기 때문에

func solution() {
	reader := bufio.NewReader(os.Stdin)
	reverse := func(s string) (ans string) {
		for i := len(s) - 1; i >= 0; i-- {
			ans += string(s[i])
		}
		return ans
	}
	strCompare := func(a string, b string, n []int) string {
		b1 := reverse(b[:n[0]])
		b2 := reverse(b[n[0]:n[1]])
		b3 := reverse(b[n[1]:])
		if a > (b1 + b2 + b3) {
			return b1 + b2 + b3
		}
		return a
	}

	var input string
	answer := "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
	fmt.Fscanln(reader, &input)

	recur := func(n int, rs []int, start, flag int) {}
	recur = func(n int, rs []int, start, flag int) {
		if len(rs) == 2 {
			answer = strCompare(answer, input, rs)
			return
		} else {
			for i := start; i < n; i++ {
				if flag&(1<<i) == 0 {
					recur(n, append(rs, i), i+1, flag|(1<<i))
				}
			}
		}
	}
	recur(len(input), []int{}, 1, 0)
	fmt.Println(answer)
}

string을 reverse 해주는 함수가 없어 따로 작성했다(그립다 java stringBuilder) answer 같은 경우는 최대 50 개의 단어가 주어지기 때문에 위와 같이 초기화시켜주었으며 조합을 응용해서 작성했다.

 

7. 부등호 [2529]

<,>  두 종류 의 부등호가 주어지고 주어진 부등호의 관계를 만족시켜야 한다는 조건이 붙는다.

부등호 앞뒤로 넣을 수 있는 숫자는 0~9까지이며 숫자의 선택은 한 번씩 만 가능하다.

k의 범위가 2~9까지 이기 때문에 나올 수 있는 숫자는 총 10자리이며 0 또한 표기해주어야 하기 때문에 스트링으로 처음부터 표기하면서 넘어가자.

func solution() {
	reader := bufio.NewReader(os.Stdin)
	var a int
	fmt.Fscanln(reader, &a)
	arr := make([]string, a)
	for i := range arr {
		var b string
		fmt.Fscan(reader, &b)
		arr[i] = b
	}

	min, max := "9999999999", "0"

	recur := func(rs []string, depth, flag int) {}
	recur = func(rs []string, depth, flag int) {
		if len(rs) >= a+1 {
			result := strings.Join(rs, "")
			if min > result {
				min = result
			}
			if max < result {
				max = result
			}
			return
		} else {
			for i := 0; i <= 9; i++ {
				if depth == 0 {
					recur(append(rs, fmt.Sprintf("%d", i)), depth+1, flag|(1<<i))
				} else {
					if flag&(1<<i) == 0 {
						next := fmt.Sprintf("%d", i)
						switch arr[depth-1] {
						case "<":
							if rs[depth-1] < next {
								recur(append(rs, next), depth+1, flag|(1<<i))
							}
						default:
							if rs[depth-1] > next {
								recur(append(rs, next), depth+1, flag|(1<<i))
							}
						}
					}
				}
			}
		}
	}
	recur([]string{}, 0, 0)
	fmt.Printf("%s\n%s", max, min)
}

최소 최댓값을 선정을 최초 그냥 스트링으로 지정하였다. 이후 기존 백트래킹 방식과 유사하게 작성하였다. 

else 구문에는 switch 구문을 이요해 케이스의 분기를 나누어 주었다. 요즘 select 구문을 자주 사용하다 보니 switch 문이 조금 더 편한 기분이기도 하다. 

 

8. 연산자 끼워넣기 [14888]

숫자 2~11개 가 주어지고 연산자는 주어진 숫자-1 만큼 주어진다. 이에 따라 숫자의 최댓값, 최솟값을 구하라는 문제이다. 

자릿수가 최대 여도 11자리 부호연산자는 10개 총 필요한 연산자는 10! 이 될듯하기 때문에 완탐으로 때려도 된다.

 

위의 대부분의 완탐의 경우에는 주어지는 숫자에 대해 재귀를 돌았다면 이번에는 정해진 operation에 의해 재귀를 돌면 된다.

func solution() {
	reader := bufio.NewReader(os.Stdin)

	var a int
	fmt.Fscanln(reader, &a)

	arr := make([]int, a)
	for i := range arr {
		fmt.Fscan(reader, &a)
		arr[i] = a
	}
	oper := make([]int, 4)
	for i := range oper {
		fmt.Fscan(reader, &a)
		oper[i] = a
	}
	min, max := 1<<31, -(1 << 31)

	recur := func(idx, sum int) {}
	recur = func(idx, sum int) {
		if idx == len(arr) {
			if min > sum {
				min = sum
			}
			if max < sum {
				max = sum
			}
			return
		} else if idx == 0 {
			recur(idx+1, arr[idx])
		} else {
			for i := 0; i < len(oper); i++ {
				if oper[i] > 0 {
					switch i {
					case 0:
						oper[i]--
						recur(idx+1, sum+arr[idx])
						oper[i]++
					case 1:
						oper[i]--
						recur(idx+1, sum-arr[idx])
						oper[i]++
					case 2:
						oper[i]--
						recur(idx+1, sum*arr[idx])
						oper[i]++
					default:
						oper[i]--
						recur(idx+1, sum/arr[idx])
						oper[i]++
					}
				}
			}
		}
	}
	recur(0, 0)
	fmt.Printf("%d\n%d", max, min)
}

연산자의 개수가 0 이상일 때만 switch 문의 재귀를 타도록 만들었으며 재귀호출 이후에는 다시 ++ 를 해주어 모든 경우에 대한 탐색 을 하고 마지막 수의 값을 min, max에 따라 가져간다.

 

9. 라그랑주의 네 제곱수 정리 [3933]

못 푼 문제이다.ㅠ  시간초과 의 벽을 어쩌지 못하고 주어지는 숫자 n에 대하여 최대 4개의 자연수의 제곱의 합이 주어지는 숫자 n과 일치하는 여부를 찾는 문제이다.

기존방식과 동일하게 백트래킹 을 사용했으나 실패했다. 시간초과로.... 그래서 방문한 부분에 대해 처리를 해주려고 

visit [][][] 이렇게 사용했다가 메모리 플로우로 터져버렸다.

풀이를 참조해 보니 그냥 4중 for 문 돌리던가 아니면 dp를 사용한다.

func solution() {
	reader := bufio.NewReader(os.Stdin)
	ans := strings.Builder{}

	getAnswer := func(n int) int {
		var cnt int
		for i := 1; i*i <= n; i++ {
			if i*i == n {
				cnt++
				continue
			} else if i*i > n {
				break
			}
			for j := i; i*i+j*j <= n; j++ {
				if i*i+j*j == n {
					cnt++
					continue
				} else if i*i+j*j > n {
					break
				}
				for k := j; i*i+j*j+k*k <= n; k++ {
					if i*i+j*j+k*k == n {
						cnt++
						continue
					} else if i*i+j*j+k*k > n {
						break
					}
					for l := k; i*i+j*j+k*k+l*l <= n; l++ {
						if i*i+j*j+k*k+l*l == n {
							cnt++
							continue
						} else if i*i+j*j+k*k+l*l > n {
							break
						}
					}
				}
			}

		}
		return cnt
	}
	for {
		var n int
		fmt.Fscanln(reader, &n)
		if n == 0 {
			break
		}
		ans.WriteString(strconv.Itoa(getAnswer(n)) + "\n")
	}

	fmt.Println(ans.String())
}

디피로 푸는 방법도 있다.

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	//fmt.Println(1 << 15)
	solution()
}

func solution() {
	reader := bufio.NewReader(os.Stdin)
	ans := strings.Builder{}
	var dp [32768][5]int
	for i := 1; i*i < 32768; i++ {
		dp[i*i][1] = 1
		for j := i * i; j < 32768; j++ {
			dp[j][2] += dp[j-i*i][1]
			dp[j][3] += dp[j-i*i][2]
			dp[j][4] += dp[j-i*i][3]
		}
	}

	getAnswer := func(n int) int {

		var cnt int
		for i := 0; i < 5; i++ {
			cnt += dp[n][i]
		}
		return cnt
	}
	for {
		var n int
		fmt.Fscanln(reader, &n)
		if n == 0 {
			break
		}
		ans.WriteString(strconv.Itoa(getAnswer(n)) + "\n")
	}

	fmt.Println(ans.String())
}

이 테이블 dp [i][j]은 “수 i를 j개의 제곱수의 합으로 표현하는 방법의 수”를 저장한다.

초기에 i*i (제곱수 자체)는 i*i를 1개의 제곱수로 표현하는 방법이므로 dp [i*i][1]=1로 설정되고.
dp를 채우는 이 반복문에서, j는 새로운 합을 나타내는 인덱스이고 i는 제곱수를 나타냅니다. j에 대해 반복할 때마다 i의 제곱값을 현재의 j에 뺀 값 (j-i*i)에 대한 DP 값을 가지고 온 후, j*(i*i)에 해당하는 값을 경신합니다. 이렇게 하면, 각 j에 대해 최대 j 개의 제곱수로 수를 표현하는 방법의 수를 누적하여 저장할 수 있다.
즉, dp [j][2]는 j를 2개의 제곱수의 합으로 표현하는 경우의 수를 나타내며, dp [j][3]과 dp [j][4] 역시 동일한 방식으로 계산된다.

 

현실적으로 이 방법에 대해 어렴풋이 느낌만 있었지 구현하라 그러면 못하지 않았을까 싶다... 

 

10. 스타트와 링크 [14889]

arr로 각  번호들의 능력치를 입력 값으로 주고 arr [i][j] + arr [j][i]는 같은 팀이 된다면 앞에와 같은 힘을 낸다 따라서 조합으로 팀원을 2개의 팀으로 구분 짓고 각각의 팀의 능력치의 최소 값을 찾아주면 된다. 

한 명의 플레이어가 선택된다면 그건 가로 세로 다 선수의 능력치를 사용할 수 없다 다시 말해 저 2차원 배열은 1차원 배열로 다시 나열될 수 있다.

위 그림에서 해당 인원들의 능력치를 다시 1차원 배열로 변경한다면 

[6 15 10 12] [14 6 12 11]  이렇게 변경될 수 있다. 이  모든 수의 합은 43이 되고 이는 모두 중복되는 값이다. 여기서 1,4를 선택한다고 하면 1(6+14), 4(12+11) 이 들어가고 total에서 빼주면 반대편 값이 나온다.

이해가 잘 안 된다면 풀어서 작성해 보자 중복된 값들의 덧셈이 존재해 이것이 가능하다.

 

1번 (6(1+2+3) + 14(4+7+3)) 4번 (12(3+4+5) + 11(3+6+2))

2번 (15(4+5+6) + 6(1+1+4)) 3번 (10(7+1+2) + 12(2+5+5))

 

위에 보이는 것처럼 중복된 값들이 계산되기 때문에 모두 더한 후 total에서 빼주게 되면 값이 일치하게 된다.

 

func solution() {
	reader := bufio.NewReader(os.Stdin)
	abs := func(a int) int {
		if a < 0 {
			return -a
		}
		return a
	}

	var a int
	fmt.Fscanln(reader, &a)

	arr := make([][]int, a)
	row := make([]int, a)
	col := make([]int, a)
	total := 0
	for i := range arr {
		sub := make([]int, a)
		for j := range sub {
			var b int
			fmt.Fscan(reader, &b)
			sub[j] = b
			total += b
			row[i] += b
			col[j] += b
		}
		arr[i] = sub
	}
	min := 1 << 31
	recur := func(start, depth, sum, flag int) {}
	recur = func(start, depth, sum, flag int) {
		if depth == a/2 {
			target := abs(total - sum)
			if target < min {
				min = target
			}
			return
		} else {
			for i := start; i < a; i++ {
				if flag&(1<<i) == 0 {
					recur(i+1, depth+1, sum+row[i]+col[i], flag|(1<<i))
				}
			}
		}
	}
	recur(0, 0, 0, 0)
	fmt.Println(min)
}

사실 해당 문제의 다른 버전을 친구에게 제공받아 풀었지만 실패하고 이 문제를 찾아서 풀게 되었다.

 

11. 링크와 스타트 [15661]

해당 문제는 위에서 언급한 것처럼 해결하지 못했다.

위와 동일한 조건이지만 단 팀이 무조건 공평한 숫자가 아닌 최소 한 명 이상만 있으면 팀의 조건을 만족하게 된다.

위에서 제시한 조건을 그대로 이용해서 사용한다면?

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	//fmt.Println(1 << 15)
	solution()
}

func solution() {
	reader := bufio.NewReader(os.Stdin)
	abs := func(a int) int {
		if a < 0 {
			return -a
		}
		return a
	}
	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}

	var a int
	fmt.Fscanln(reader, &a)

	arr := make([][]int, a)
	row := make([]int, a)
	col := make([]int, a)
	total := 0
	for i := range arr {
		sub := make([]int, a)
		for j := range sub {
			var b int
			fmt.Fscan(reader, &b)
			total += b
			row[i] += b
			col[j] += b
		}
	}

	res := 1 << 31
	recur := func(idx, cur int) {}
	recur = func(idx, cur int) {
		res = min(res, abs(cur))
		for i := idx + 1; i < a; i++ {
			recur(i, cur-row[i]-col[i])
		}
	}

	recur(0, total)
	fmt.Println(res)
}

계산된 total 값을 이용해 한 칸씩 없애주면 된다. 오셀로 하듯이

 

나는 완탐을 잘못하기 때문에 이렇게 하루 쉬는날을 이용해서 풀었던 완탐을 정리해 봤다.

또 하루 날 잡고 완탐에 대해 다시 풀어보고자 한다.

완벽하게 완탕이 될 때까지 해보고 싶다.