글 읽기 - GO 언어로 36진수 덧셈 풀었는데, 어디가 문제일까요?

taewony 7년 전 0

안녕하세요?

GO 언어로 문제풀이를 해 보고 있는데, 졸지에 1036번에 막혀 진도가 나가지 못하고 있네요.

(문제 번호가 작다고 우습게 볼게 아니군요,

그리고 역시 언어가 좋고 나쁘고가 문제가 아니라, 문제 풀이 자체가 어렵네요.)

3일째 같은 문제 놓고 낑낑거리고 있습니다. 힌트 좀 부탁할 수 있을까요?

-- 혼자 생각해 보는 test 방법 ---

- 36진수 덧셈이 맞게 되었는지 확인해 보기 위해 합에서 다시 빼서 zero가 나오는 지 확인해 본다.

- 모두 동일한 수들이 주어진 경우, 앞에서부터 k개까지 Z로 바꾸고 더한 경우와

같아야 한다.

package main

import (
	"fmt"
	"sort"
)

var used [36]bool

type data struct {
	key, num, idx, pos int
}
type dataList []data

func (d dataList) Len() int {
	return len(d)
}
func (d dataList) Less(i, j int) bool {
	return d[i].key > d[j].key
}
func (d dataList) Swap(i, j int) {
	d[i], d[j] = d[j], d[i]
}

func gainCalc(s, p int) (int, int) {
	gain := 36*p + 35 - s
	return gain, s
}

type numb36 struct {
	digit [54]int
}

func (n *numb36) reverseStr() string {
	var str string
	zero := true
	for i := 53; i >= 0; i-- {
		if zero {
			if n.digit[i] > 0 {
				zero = false
				s := itoa36(n.digit[i])
				str = string(s) + str
			}
		} else {
			s := itoa36(n.digit[i])
			str = str + string(s)
		}
	}
	if zero {
		str = "0"
	}
	return str
}
func (n *numb36) add36(s string) {
	s = reverse(s)
	for i := 0; i < len(s); i++ {
		d := atoi36(s[i])
		added := d + n.digit[i]
		if added > 35 {
			n.digit[i] = added - 36
			n.digit[i+1]++
		} else {
			n.digit[i] = added
		}
	}
	i := len(s)
	for ; n.digit[i] > 35; i++ {
		n.digit[i] -= 36
		n.digit[i+1]++
	}
}

func main() {
	var n int
	fmt.Scan(&n)

	strs := []string{}
	var nums dataList

	for idx := 0; idx < n; idx++ {
		var str string // := "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"
		fmt.Scan(&str)
		strs = append(strs, str)

		for i := 0; i < len(str); i++ {
			g, s := gainCalc(atoi36(str[i]), len(str)-i-1)
			d := data{g, s, idx, i}
			nums = append(nums, d)
		}
	}
	sort.Sort(nums)

	var k int
	fmt.Scan(&k)
	for _, num := range nums {
		idx := num.idx
		pos := num.pos
		if used[num.num] {
			strs[idx] = strs[idx][:pos] + string('Z') + strs[idx][pos+1:]
		} else {
			if k > 0 {
				k--
				used[num.num] = true
				strs[idx] = strs[idx][:pos] + string('Z') + strs[idx][pos+1:]
			}
		}
	}

	var sum numb36
	for _, str := range strs {
		sum.add36(str)
	}
	sumStr := sum.reverseStr()
	fmt.Println(sumStr)
}

func atoi36(c byte) int {
	if c >= 'A' {
		return int(c-'A') + 10
	}
	return int(c - '0')
}

func itoa36(c int) int {
	if c >= 10 {
		return (c - 10) + 'A'
	}
	return c + '0'
}

func reverse(s string) string {
	r := []rune(s)
	for i, j := 0, len(r)-1; i < len(r)/2; i, j = i+1, j-1 {
		r[i], r[j] = r[j], r[i]
	}
	return string(r)
}

bupjae 7년 전 2

다음과 같이 데이터가 주어졌을 때

W를 Z로 바꾸는 것이 최적해 (44063 + 1295 * 49 = 107518 => 2AYW)이지만

작성하신 프로그램은 X를 Z로 바꾸고 있습니다 (46544 + 1184 * 49 = 104560합 => 28OG)

50
XWW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
WW
1

taewony 7년 전 0

@bupjae 님 힌트에 힘입어 해결 했습니다. 감사해요 ㅠㅜ

최선의 k개의 숫자를 고를 때, 단지 자리값만 보고 고르지 않고, Z로 바꾸었을 때 전체적인 차이가 최대가 되도록 logic을 수정했습니다.

역시 풀고 나니 개운하네요 크하하^^ 다음 문제는 좀 쉽기를 ㅎㅎㅎ

nlkey2022 6년 전 1

@bupjae 님 위 예제 결과는 2AYM 아닌가요?.. (35 * 50 )%36는 22라 M가 맞지 않나요?..

bupjae 6년 전 0

@nlkey2022 :: 2AYM 이 맞네요. 지적 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

GO 언어로 36진수 덧셈 풀었는데, 어디가 문제일까요?

taewony 7년 전 0

bupjae 7년 전 2

taewony 7년 전 0

nlkey2022 6년 전 1

bupjae 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말