백준 15662번 - 톱니바퀴 (2) (Go)

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

 

분석

이 문제는 주어진 조건에 따라 여러 개의 톱니바퀴를 회전시키는 시뮬레이션 문제입니다.

시간복잡도는 회전 횟수 k번 동안 최대 t개의 톱니바퀴를 검사하고 회전시켜야 하므로 O(k * t)$입니다. 1,000 * 1,000 = 1,000,000으로 2초라는 시간 제한 내에 충분히 여유롭게 통과 가능합니다.

공간복잡도는 톱니바퀴 상태를 저장하는 int 형 2차원 배열 O(t * 8)$입니다. 8 byte * 1,000 * 8은 약 64KB 정도로 매우 여유롭습니다.

 

알고리즘 로직을 생각해 보면,

1. 연쇄 회전 결정:
   • 특정 톱니바퀴가 회전할 때, 양옆의 톱니바퀴가 함께 회전할지 여부를 먼저 결정해야 합니다.
   • 회전이 실제로 일어나기 전의 상태를 기준으로 맞닿은 극(2번 인덱스와 6번 인덱스)을 비교합니다.
2. 방향 전파:
   • 기준 바퀴의 왼쪽 방향과 오른쪽 방향으로 각각 전파하며, 인접한 바퀴가 회전한다면 기준 바퀴와 반대 방향으로 회전시킵니다.
   • 만약 극이 같아 회전하지 않는다면 그 이후의 바퀴들도 영향을 받지 않습니다.
3. 톱니바퀴 회전:
   • 시계 방향(1)은 마지막 요소를 맨 앞으로, 반시계 방향(-1)은 첫 번째 요소를 맨 뒤로 보냅니다.
4. 결과 계산:
   • 모든 회전 명령을 수행한 후, 각 톱니바퀴의 12시 방향(0번 인덱스)이 S극(1)인 개수를 셉니다.

풀이 코드

package main

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

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var t int
	fmt.Fscan(in, &t)

	gears := make([][]int, t)
	for i := 0; i < t; i++ {
		var s string
		fmt.Fscan(in, &s)

		gears[i] = make([]int, 8)
		for j := 0; j < 8; j++ {
			gears[i][j] = int(s[j] - '0')
		}
	}

	var k int
	fmt.Fscan(in, &k)

	for i := 0; i < k; i++ {
		var num, dir int
		fmt.Fscan(in, &num, &dir)
		num--

		rotations := make([]int, t)
		rotations[num] = dir

		for j := num - 1; j >= 0; j-- {
			if gears[j][2] != gears[j + 1][6] {
				rotations[j] = -rotations[j + 1]
			} else {
				break
			}
		}

		for j := num + 1; j < t; j++ {
			if gears[j][6] != gears[j - 1][2] {
				rotations[j] = -rotations[j - 1]
			} else {
				break
			}
		}

		for j := 0; j < t; j++ {
			if rotations[j] != 0 {
				rotate(gears[j], rotations[j])
			}
		}
	}

	res := 0
	for i := 0; i < t; i++ {
		if gears[i][0] == 1 {
			res++
		}
	}

	fmt.Fprintln(out, res)
}

func rotate(gear []int, dir int) {
	if dir == 1 {
		last := gear[7]

		for i := 7; i > 0; i-- {
			gear[i] = gear[i - 1]
		}

		gear[0] = last
	} else {
		first := gear[0]

		for i := 0; i < 7; i++ {
			gear[i] = gear[i + 1]
		}
		
		gear[7] = first
	}
}

 

회고

단순한 시뮬레이션 문제였습니다.