글 읽기 - 3101 토끼의 이동 푸신 분?!

mingo2017 3년 전 0

n을 십만을 넣으면 메모리 초과가 뜨는데요 ㅠ.ㅠ

어떻게 해결할 수 있을까요?

문제 조건에 이 값은 32비트 정수를 넘을 수도 있다. 라는 내용이 있습니다...

배열을 만들지 않고 패턴을 찾아서 해결해야 하나요?

import java.util.*;

public class Main {
	static int num, cnt, x, y, n, m, sx, sy;
	static long sum, ans;
	static Queue<Character> order = new LinkedList<Character>();
	static long[][] a;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		sc.nextLine();
		String s = sc.nextLine();

		for (int i = 0; i < s.length(); i++) {
			order.add(s.charAt(i));
		}
		a = new long[100001][100001];

		cnt = 1;
		num = 1;

		x = 0;
		y = 0;
		sum = 0;
		makemap();
		//confirm();
		sx = 0;
		sy = 0;
		sum += a[sx][sy];
		go();
		System.out.println(sum);

	}

	private static void go() {
		while (!order.isEmpty()) {
			char o = order.remove();

			if (o == 'D') {
				sx += 1;
			} else if (o == 'U') {
				sx -= 1;
			} else if (o == 'R') {
				sy += 1;
			} else if (o == 'L') {
				sy -= 1;
			}

			sum += a[sx][sy];

		}
	}

	private static void confirm() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(a[i][j] + "  ");
			}
			System.out.println();
		}
		System.out.println();
	}

	private static void makemap() {
		for (int k = 1; k < n; k++) {
			cnt = 1;
			for (int t = 1; t <= k; t++) {

				a[x][y] = num++;
				cnt += 1;

				if (cnt > k) { // 다른 대각선 이동

					if (k % 2 == 0) {
						x += 1;
					} else if (k % 2 != 0) {
						y += 1;
					}

				} else { // 대각선 내부 이동
					if (k % 2 == 0) { // 짝수 대각선
						x += 1;
						y -= 1;
					} else if (k % 2 != 0) { // 홀수 대각선
						x -= 1;
						y += 1;
					}
				}
			}
		}

		for (int k = n; k > 0; k--) {
			cnt = 1;

			for (int t = 1; t <= k; t++) {

				a[x][y] = num++;
				cnt += 1;

				if (cnt > k) { // 다른 대각선 이동

					if (k % 2 == 0) {
						y += 1;
					} else if (k % 2 != 0) {
						x += 1;
					}

				} else { // 대각선 내부 이동
					if (k % 2 == 0) { // 짝수 대각선
						x += 1;
						y -= 1;
					} else if (k % 2 != 0) { // 홀수 대각선
						x -= 1;
						y += 1;
					}
				}
			}
		}

	}

}

cheetose 3년 전 1

이 문제를 풀어보진 않았지만 현재 좌표에 있는 숫자를 바로 알아내는 방법이 있습니다.

mingo2017 3년 전 0

어떻게 구현해야 할까요? ㅜ.ㅜ

cheetose 3년 전 2

제목 없음.png

이런 식으로 했을 때, 각 좌표 별로 몇 번째 라인인지 O(1)로 알 수 있고(식은 밍고님이 직접 짜보세요!)

라인이 홀수번째냐, 짝수번째냐만 나누면 역시 O(1)에 현재 위치의 값을 알 수 있습니다.

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

문제

문제

출처

ICPC

3101 토끼의 이동 푸신 분?!

mingo2017 3년 전 0

cheetose 3년 전 1

mingo2017 3년 전 0

cheetose 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말