All Articles

๋ฐฑ์ค€ 15685๋ฒˆ

ํ’€๊ณ ๋‚˜์„œ ํ’€์ด๋ฅผ ์ฐพ์•„๋ณด๋‹ˆ ๋‹ค๋“ค ์Šคํƒ์œผ๋กœ ํ’€์–ด์„œ ๊ทธ๋ ‡๊ฒŒ ๋จธ๋ฆฌ๋ฅผ ์•ˆ์จ๋„ ํ’€๋ฆฌ๋Š” ๋ฌธ์ œ๋ผ๋Š” ๊ฒƒ์„ ๋‚จ๊ธฐ๋ ค๊ณ  TIL์— ๋‚จ๊น€.

์žฌ๊ท€์ ์œผ๋กœ g = N์ธ ๊ทธ๋ฆผ์„ ๊ทธ๋ฆด ๊ฒฝ์šฐ

  1. g = 1 ๋ฐฉํ–ฅ๋”ฐ๋ผ ์ž˜ ๊ทธ๋ฆผ (๊ธฐ์ € ์ผ€์ด์Šค)
  2. g = N-1 ์ธ ๊ทธ๋ฆผ์„ ์‹œ์ž‘์ ์—์„œ ์šฐ์„  ๊ทธ๋ฆฌ๊ณ 
    • ์‹œ์ž‘์—์„œ ๋์ ๊นŒ์ง€ ์–ผ๋งˆ๋‚˜ ๋ณ€ํ–ˆ๋‚˜๋ฅผ ๋ณด๊ณ 
    • ๋จผ์ € ๊ทธ๋ฆฐ ๊ทธ๋ฆผ์˜ ๋์ ์— ๋‹ฟ๊ฒŒ ์•Œ๋งž๊ฒŒ ์‹œ์ž‘์ ๊ณผ ๊ฐ๋„๋ฅผ ์ •ํ•ด์„œ g = N-1์ธ ๊ทธ๋ฆผ์„ ๊ทธ๋ฆฌ๋ฉด

๋œ๋‹ค. ๋ฌผ๋ก  ์ฝ”๋“œ๋ฅผ ๋Œ๋ฆฌ๋Š” ์ปดํ“จํ„ฐ ์ž…์žฅ์—์„œ๋Š” ์Šคํƒ์„ ์ด์šฉํ•œ ํ’€์ด๊ฐ€ ํ›จ์”ฌ ๊น”๋”ํ•˜๊ฒ ๋‹ค. ์‹ค์ œ ์ฑ„์  ์กฐ๊ฑด์—์„œ๋Š” ๋‘˜ ๋‹ค ํ†ต๊ณผํ•˜๋Š”์ง€ ์ž˜ ๋ชจ๋ฅด๊ฒ ๋‹ค.

#include <vector>
#include <utility>
#include <iostream>

using namespace std;

vector<vector<bool> > map;
// (x, y)

vector<vector<int> > dirs = {
	{1, 0},
	{0, -1},
	{-1, 0},
	{0, 1}
};


int nextDir, firstDx, firstDy, secondDx, secondDy;

pair<int, int> draw(vector<vector<bool> >& rmap, pair<int, int> start, int dir, int gen) {
    // ๋‹ค ๊ทธ๋ฆฌ๊ณ ์„œ ๋์ ์˜ ์œ„์น˜๋ฅผ ๋ฐ˜ํ™˜
	if (gen == 0) { // basecase
		int x = start.first;
		int y = start.second;

		int newX = x + dirs[dir][0];
		int newY = y + dirs[dir][1];

		rmap[newX][newY] = true;
		rmap[x][y] = true;
		return make_pair(newX, newY);
	}

	pair<int, int> firstEnd = draw(rmap, start, dir, gen - 1); // ๋จผ์ € ์ฒซ๋ฒˆ์งธ ํŒŒํŠธ๋ฅผ ๊ทธ๋ฆฌ๊ณ 
	firstDx = firstEnd.first - start.first; 
	firstDy = firstEnd.second - start.second; 
    // ์ฒซ๋ฒˆ์งธ ํŒŒํŠธ์—์„œ ์‹œ์ž‘ -> ๋์˜ ๋ณ€ํ™”๋Ÿ‰์„ ๊ตฌํ•˜๊ณ 

	secondDx = -firstDy; // ๊ทธ๊ฑธ ์˜ค๋ฅธ์ชฝ์œผ๋กœ 90๋„ ํšŒ์ „ํ•ด์„œ
	secondDy = firstDx;
	nextDir = dir == 0 ? 3 : dir - 1;

    //์ฒซ๋ฒˆ์งธ ๋ถ€๋ถ„์ด ๋๋‚œ ๊ณณ์—์„œ dx,dy ๋งŒํผ ๋’ค๋กœ ๊ฐ€์ฃผ๋ฉด ๋‘๋ฒˆ์งธ ๋ถ€๋ถ„์„ ์‹œ์ž‘ํ•ด์•ผํ•  ์œ„์น˜๊ฐ€ ๋‚˜์˜ด
	pair<int, int> secondStart = make_pair(firstEnd.first - secondDx, firstEnd.second - secondDy);
	draw(rmap, secondStart, nextDir, gen - 1);

	return secondStart;
}

int main() {
	int N;
	cin >> N;

	map = vector<vector<bool> >(102, vector<bool>(102, false));

	int x, y, d, g;
	for (int i = 0; i < N; i++) {
		cin >> x >> y >> d >> g;
		draw(map, make_pair(x, y), d, g);
	}

	int count = 0;
	for (int i = 0; i < 101; i++) {
		for (int j = 0; j < 101; j++) {
			if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
				count++;
			}
		}
	}

	cout << count << endl;

	return 0;
}

Published Oct 14, 2018

If I keep marking the dots, someday they will ๐Ÿ”—๐Ÿ”—