수행시간이 너무 오래걸려서 시간을 줄임
먼저 코드는 일일이 다 찾아보고 카운트를 증가시켰다면 이번엔 위치를 먼저 찾고 값을 구함
코드 길이는 좀 더 늘어났지만 시간은 대폭 줄일 수 있었음
위치를 찾고 나서 값을 구하는 게 어려웠다..
어떻게 다시 재귀호출 할 것인지 매개변수를 설정해주는 게 어려웠음
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace _1074
{
class Program
{
static void Main(string[] args)
{
string[] str = Console.ReadLine().Split(' ');
int n = int.Parse(str[0]);
int r = int.Parse(str[1]);
int c = int.Parse(str[2]);
int size = (int)Math.Pow(Math.Pow(2, n), 2);
Z z = new Z();
z.Search(n, r, c, size);
}
}
class Z
{
int result = 0;
public void Search(int n, int r, int c, int size)
{
if (n==0)
{
return;
}
if(r-Math.Pow(2,n)/2<0 && c-Math.Pow(2,n)/2<0)
{
if(n==1)
{
Console.WriteLine(result);
return;
}
else
{
this.Search(n - 1, r, c, size/4);
}
}
else if (r - Math.Pow(2, n) / 2 < 0 && c - Math.Pow(2, n) / 2 >= 0)
{
if (n == 1)
{
result += 1;
Console.WriteLine(result);
return;
}
else
{
result += size / 4;
this.Search(n - 1, r, c-(int)Math.Pow(2,n-1), size/4);
}
}
else if (r - Math.Pow(2, n) / 2 >= 0 && c - Math.Pow(2, n) / 2 < 0)
{
if (n == 1)
{
result += 2;
Console.WriteLine(result);
return;
}
else
{
result += size / 4*2;
this.Search(n - 1, r - (int)Math.Pow(2, n - 1), c, size/4);
}
}
else if (r - Math.Pow(2, n) / 2 >= 0 && c - Math.Pow(2, n) / 2 >= 0)
{
if (n == 1)
{
result += 3;
Console.WriteLine(result);
return;
}
else
{
result += size / 4*3;
this.Search(n - 1, r - (int)Math.Pow(2, n - 1), c - (int)Math.Pow(2, n - 1), size/4);
}
}
}
}
}
-----------------------------------------------------------------------------------------------------------------------------
문제에 2차원 배열 써있길래 진짜 2차원 배열 만들어야하는 줄 알고 만들어서 접근하다가
갈수록 이게 아니구나 싶어서 다시 풀어내느라 오래 걸림
사이즈를 입력받으면 다시 재귀호출해서 2 * 2 사이즈로 만들어가면서 푸는 문제였다
Z가 처음 시작되는 곳 찾는건 어렵지 않았는데
두번째로 숫자 채워지는 곳에 접근하는 걸 좀 헤맴
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace _1074
{
class Program
{
static int count;
static int N;
static int r;
static int c;
static void Main(string[] args)
{
string[] input = Console.ReadLine().Split(' ');
N= int.Parse(input[0]);
r = int.Parse(input[1]);
c = int.Parse(input[2]);
int x = 0;
int y = 0;
if(N>=1 && N<=15)
{
int size = 1;
for(int i=0; i<N; i++)
{
size *= 2;
}
Search(size, x, y);
}
}
static void Search(int size,int x,int y)
{
if(size==2)
{
if(x==r && y ==c)
{
Console.WriteLine(count);
return;
}
count++;
if (x==r && y+1==c)
{
Console.WriteLine(count);
return;
}
count++;
if (x+1 == r && y == c)
{
Console.WriteLine(count);
return;
}
count++;
if (x + 1 == r && y + 1 == c)
{
Console.WriteLine(count);
return;
}
count++;
}
else
{
Search(size / 2, x, y);
Search(size / 2, x, y+size/2);
Search(size / 2, x+size/2, y);
Search(size / 2, x+size/2, y+size/2);
}
}
}
}
|
1074번: Z
한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 ��
www.acmicpc.net
'C# > 알고리즘' 카테고리의 다른 글
| 14. 4963번 섬의 개수 (0) | 2020.09.05 |
|---|---|
| 13. 1967번 트리의 지름 (0) | 2020.07.26 |
| 11. 2504번 괄호의 값 (해결) (0) | 2020.06.22 |
| 10. 10845번 큐 (해결) (0) | 2020.06.21 |
| 9. 1302번 베스트셀러 (LINQ group by) (0) | 2020.06.07 |