문제 : https://www.acmicpc.net/problem/15681

문제해석

 루트가 정해진 트리가 주어졌을 때, 임의의 노드의 SubTree의 크기를 구하자.

 이때, 트리가 이진트리! 라는 말이 없으므로 조심해야한다.

문제핵심

 이 문제의 핵심은 SubTree의 크기를 구해야되는 쿼리가 10^5번 들어올 수 있기 때문에, 처음에 Root부터 시작해서 모든 노드의 SubTree의 크기를 구해둬야한다. ( 그렇게 안해도 시간 초과가 안나오는지는 모르겠습니다! ) 쿼리마다 구하면 아마 시간초과가 나올 것 같다.

알고리즘

 TreeDp를 이용해서 Root 부터 시작해서 재귀적으로 모든 노드들의 SubTree 의 크기를 구해야한다. 현재 노드가 연결된 노드들이 이미 다 방문한 노드라면, 해당 노드는 leaf 노드 이므로 Dp 값은 0이고, 1을 return 해주면 된다. leaf 노드가 아니라면 자식 노드들의 subTree 값을 모두 더해서 저장하고, 자기 자신을 포함해서 subTree + 1 값을 return 해주면 된다.

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
#include<iostream>
#include<vector>
using namespace std;
int subtree[100001];
vector<int> tree[100001];
bool visited[100001];
int countSubtree(int cur) {
    // 연결된 애들 중에 더 이상 체크할게 없을 때 --> leaf 노드일 때 1
    bool check = false;
    int sum = 0;
    for (int i = 0; i < tree[cur].size(); i++) {
        int next = tree[cur][i];
        if (!visited[next]) {
            visited[next] = 1;
            sum += countSubtree(next);
            check = true;
        }
    }
    if (!check) return 1;
    subtree[cur] = sum;
    return subtree[cur] + 1;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N, R, Q, u, v;
    cin >> N >> R >> Q;
    for (int i = 0; i < N - 1; i++) {
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    visited[R] = 1;
    countSubtree(R);
    for (int i = 0, x; i < Q; i++) {
        cin >> x;
        cout << subtree[x] + 1 << '\n';
    }
    return 0;
}
 cs

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 18809 : Gaaaaaaaaaarden  (0) 2020.07.02
[BOJ] 3109 : PLINOVOD  (0) 2020.07.01
[BOJ] 18235 : 지금 만나러 갑니다  (0) 2020.06.25
[BOJ]15591 : MooTube(Silver)  (0) 2020.06.22
[BOJ] 10021 : Watering the Fields  (0) 2020.06.22

안녕하세요, 여행벌입니다.

오늘은 자바 5에서 처음 소개가 되어 자바 8까지 상당히 많은 내용이 발전된 문법 '제네릭' 에 대해서 포스팅해보도록 하겠습니다.

기본 문법 구조부터 얻는 이점, 특징까지 차근차근 정리해보겠습니다.

제네릭(Generics)

 제네릭이란 말 그대로 "일반화" 입니다. 자바에서의 제네릭은 "자료형"을 일반화하는 문법입니다.

 즉, 자료형을 일반화시켜서 자료형에 의존적이지 않은 클래스나 메소드를 정의할 수 있습니다.

제네릭클래스(Generics Class)

 제네릭은 자료형을 일반화시킨다고 했습니다. 자료형을 정하긴 정해야하는데 그럼 어떻게 정하길래, 자료형을 일반화시킨다고 말할까요??

 제네릭은 클래스 내부에서 사용할 데이터 타입을 외부에서 지정하는 기법입니다.

 제네릭 기법을 이용해 Box 라는 이름의 클래스를 만들어 보았습니다. 자료형을 일반화시키기 위해 T 라는타입매개변수를 이용했고, 인스턴스를 생성할 때, 외부에서 자료형을 지정하는 모습을 볼 수 있습니다.

 또, 클래스 이름인 Box 옆에 <T> 라고 기술해줘야 "T는 인스턴스 생성 시 자료형을 결정할 거에요." 라고 자바에게 알려 줄 수 있습니다.

 이처럼 제네릭 기법을 활용하면 자료형에 의존적이지 않은 클래스를 만들어서 사용할 수 있습니다.

제네릭 기본 용어

T : 타입매개변수(Type Parameter)

Box<String> 에서 String : 타입 인자(Type Argument)

Box<String> : 매개변수화 타입(Parameterized Type)     이라고 부릅니다.

타입매개변수 규칙

 제네릭을 이용하기 위해서는 3가지 타입매개변수 규칙을 지켜줘야 합니다.

1. 타입매개변수는 한 문자로 이름을 짓는다.

2. 타입매개변수의 이름은 대문자로 짓는다.

3. 타입매개변수에는 기본 자료형을 넘겨줄 수 없다.

 보통 T(Type), V(Value), N(Number), K(Key), E(Element) 를 많이 이용하고 Box<int> 와 같이 타입매개변수에 기본 자료형을 넘겨줄 수 없습니다. 하지만, Wrapper 클래스를 이용하면 되기 때문에 문제는 없습니다.

타입인자 생략

1
Box<String> box1 = new Box<String>();
 cs

 인스턴스를 생성할 때 위와 같이 타입 인자를 지정해줘야 합니다. 하지만, 아래와 같이 타입 인자를 생략할 수도 있습니다.

1
Box<String> box1 = new Box<>();
 cs

 자바컴파일러가 Box<String> box1 을 보고 타입 인자가 String 인 것을 유추할 수 있기 때문입니다.

제네릭클래스 생성자

 제네릭클래스도 당연히 클래스 생성자가 있어야합니다. 일반적인 클래스 생성자와 문법은 동일합니다. 

1
2
3
4
5
6
class Box<T>{
    T box;
    public Box(T box) {
        this.box = box;
    }
}
 cs

제네릭클래스 이점

 분명, 자바의 모든 객체는 Object 를 상속한다고 했습니다. 클래스나 메소드를 Object 자료형으로 만든다면, 자료형에 얽매이지않는 클래스나 메소드를 만들 수 있지 않을까요?? 물론, Object를 이용해서 제네릭 문법을 활용한 클래스와 동일한 작업을 하도록 구현 할 수 있습니다.

 그렇다면 제네릭 클래스를 사용하면 무슨 이점이 있을까요??

 

 똑같은 작업을 제네릭클래스와 Object를 이용한 클래스로 각각 구현해나가며 알아보겠습니다.

 

1) 과일을 담을 수 있는 Box를 만든다.

2) Box에 어떤 과일을 담는다.

3) Box에 담긴 과일을 꺼낸다.

 

 먼저, 일반적인 클래스를 정의하고 이를 이용해 Box 에 Apple 을 담았다가 꺼내보겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Box{
    Object o;
    public Box(Object o) {
        this.o = o;
    }
    Object get() {
        return o;
    }
}
 
class Apple{ }
class Strawberry{ }
class Melon { }
 
public class test{
    public static void main(String args[]) {
        Box appleBox = new Box(new Apple());
        Apple apple1 = (Apple)appleBox.get();
    }
}
 
 cs

 자바의 모든 객체는 Object를 상속한다는 점을 이용해 Object를 담는 Box를 만들었습니다. 그 후, Apple을 Box에 담았다가, Box에서 get 메소드를 이용해 꺼내보았습니다.

 우리는 Box에 어떤 값도 넣을 수 있고, 어떤 값도 꺼낼 수 있기를 원하기 때문에 Object로 잘 구현했습니다. 그럼, 이 코드의 불편한 점은 무엇일까요?? 바로 get 메소드를 이용할 때 형변환을 항상 해야된다는 점입니다! 우리는 Box에 Apple 클래스를 넣을 수도 있고, Melon 클래스를 넣을 수도 있습니다. 따라서 get 메소드에서는 Object를 return 해주게되고, 우리가 원하는 자료형으로 다시 형 변환을 해야 한다는 불편함이 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Box<T>{
    T box;
    public Box(T box) {
        this.box = box;
    }
    T get() {
        return box;
    }
}
 
class Apple{ } 
class Strawberry{ } 
class Melon { }
 
public class test{
    public static void main(String args[]) {
        Box<Apple> appleBox = new Box(new Apple());
        Apple apple1 = appleBox.get();
    }
}
 cs

제네릭 클래스를 이용한다면 위와 같이 형 변환 없이도 같은 기능을 구현할 수 있습니다.

 

 또, 제네릭 클래스는 다음과 같은 이점이 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Box{
    Object o;
    public Box(Object o) {
        this.o = o;
    }
    Object get() {
        return o;
    }
}
 
class Apple{ }
class Strawberry{ }
class Melon { }
 
public class test{
    public static void main(String args[]) {
        Box box1 = new Box("Apple");
        box1.get();
    }
}
 cs

 우리는 Box 클래스를 정의할 때, "과일을 담는 박스" 라고 정의했습니다. 하지만, 지금 "Apple" 이라는 문자열을 Box에 저장하고 get() 메소드를 이용하고 있습니다. 문법적으로 문제가 있을까요?? String 도 Object 를 상속하기 때문에 개발자의 의도와 전혀 다르게 Box가 사용되고 있지만 컴파일 단계에서 문제가 드러나지 않습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Box<T>{
    T box;
    public Box(T box) {
        this.box = box;
    }
    T get() {
        return box;
    }
}
 
class Apple{ }
class Strawberry{ }
class Melon { }
 
public class test{
    public static void main(String args[]) {
        Box<Apple> box1 = new Box<>("Apple");
        box1.get();
    }
}
 cs

 제네릭 클래스를 이용하면 <Apple> 을 담을 Box를 만들기 때문에 위와 같이 문자열을 잘못 입력하면 컴파일 단계에서 에러가 드러납니다.

1
2
3
4
Exception in thread "main" java.lang.Error: Unresolved compilation problem: 
    Cannot infer type arguments for Box<>
 
    at HelloWorld/Hello.test.main(test.java:19)
 cs

 제네릭 클래스를 이용하면 위에서 보았듯이, 형 변환을 하지 않아도 되고, 자료형과 관련된 실수가 컴파일 단계에서 드러난다는 굉장히 큰 이점이 있습니다.

제네릭 메소드

 메소드도 클래스와 마찬가지로 제네릭 문법을 이용해서 "자료형"에 의존적이지 않은 메소드를 만들 수 있습니다. 기본 구조는 다음과 같습니다.

1
<T> 반환형 메소드이름(매개변수)
 cs

 <T> 를 통해서 이 메소드는 제네릭 메소드입니다! 라고 자바 머신에게 알려줍니다.

 그럼 제네릭 메소드를 활용해서 위에서 만들었던 제네릭 클래스 Box의 내용물을 꺼내오는 메소드를 만들어보겠습니다.

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
class Box<T>{
    T box;
    public Box(T box) {
        this.box = box;
    }
    T get() {
        return box;
    }
}
 
class Opener{
    public static <T> T open(Box<T> box) {
        return box.get();
    }
}
 
class Apple{ }
class Strawberry{ }
class Melon { }
 
public class test{
    public static void main(String args[]) {
        // box1 에 Apple 을 담았습니다.
        Box<Apple> box1 = new Box<>(new Apple());
        // Opener 클래스의 open 메소드를 통해 상자에 담겨있는 Apple을 꺼냅니다.      
        Apple apple1 = Opener.open(box1);
    }
}
 cs

 제니릭 클래스를 매개변수로 받아 안에 있는 내용물을 return 해주는 open 제네릭 메소드를 만들었습니다. 우리가 기존에 알던 메소드와 구조적으로 크게 다른 점은 없으나 "자료형" 을 일반화 시킬 수 있습니다. 즉, 박스에 어떤 자료형이 담겨있어도 꺼내올 수 있는 메소드입니다.

이번 포스팅에서는 제네릭 클래스의 기본 문법 구조 위주로 알아보았습니다.

다음 포스팅에서는 더 나아가 고급 제네릭 기법에 대해서도 다뤄보겠습니다.

 

 

 

'Computer Language > JAVA' 카테고리의 다른 글

[JAVA] #31 Collection<E> 인터페이스  (0) 2020.07.03
[JAVA] #30 자바 컬렉션프레임워크(Collection Framework)  (0) 2020.07.03
[JAVA] #28 BigInteger 클래스 정리  (0) 2020.06.26
[JAVA] #27 Integer 클래스 메소드 정리  (0) 2020.06.25
[JAVA] #26 자바 Number 클래스 메소드 정리  (0) 2020.06.23

안녕하세요, 여행벌입니다.

오늘은 자바 BigInteger 클래스에 대해 알아보고, 메소드를 정리해보겠습니다.

BigInteger 클래스

 BigInteger 클래스는 클래스 이름 그대로, 큰! 정수를 다루기 위해 등장한 클래스입니다. 우리는 정수를 int, long 기본 자료형으로 표현할 수 있습니다. 하지만, int, long 은 모두 표현할 수 있는 값의 크기가 한계가 있습니다. 그러면, long 형 범위보다도 큰 값을 JAVA 에서는 표현할 수 없을까요?

 이를 해결하기 위해 자바에서는 BigInteger 클래스를 지원해줍니다.

 Wrapper 클래스들과 마찬가지로, Number 클래스를 상속하고 있습니다.

1
import java.math.BigInteger;
 cs

 내장클래스가 아니므로 사용하기 위해서는BigInteger 클래스를 import 해와야 합니다.

BigInteger(String val)

 가장 자주 쓰이는 BigInteger 생성자 입니다. long 형을 벗어나는 범위의 값을 표현해야 하기 때문에 입력을 int, long 이 아닌 String 으로 받고 있습니다.

1
2
3
4
5
6
7
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        new BigInteger("10000000000000000000000000");
    }
}
 cs

 long 형으로도 표현할 수 없는 숫자 10000000000000000000000000 를 담고 있는 BigInteger 인스턴스를 만들었습니다.

BigInteger(String val, int radix)

 자주 쓰이는 생성자로 몇 진법으로 표현한 숫자인지 입력하는 생성자가 있습니다.  

1
2
3
4
5
6
7
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        System.out.println(new BigInteger("55555555555555555555555555555",8));
    }
}
 cs

 8진법으로 표현한 55555555555555555555555555555 로 출력해보면 10진법 110530360650480381687421805와 같다는 것을 알 수 있습니다.

public BigInteger add(BigInteger val)

 thir + val 를 BigInteger 로 return해줍니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println(num1.add(num2));
    }
}
 cs

public BigInteger subtract(BigInteger val)

 this - val 를 BigInteger로 return 해줍니다.

1
2
3
4
5
6
7
8
9
10
11
12
package Hello;
 
 
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println(num1.subtract(num2));
    }
}
 cs
1
2
[Output]
뺄셈 결과 : 1823989474918455473622288929145
 cs

public BigInteger multiply(BigInteger val)

 this * val 를 BigInteger로 return 해줍니다.

1
2
3
4
5
6
7
8
9
10
11
12
package Hello;
 
 
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println("곱셈 결과 : " + num1.multiply(num2));
    }
}
 cs

public BigInteger divide(BigInteger val)

 this / val 를 BigInteger 로 return 해줍니다. 이때, val 가 0이라면 ArithmeticException 에러가 발생합니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println("나눗셈 결과 : " + num1.divide(num2));
    }
}
 cs

public BigInteger remainder(BigInteger val)

 this % val 를 BigInteger 로 return 해줍니다. 이때, val 가 0이라면 ArithmeticException 에러가 발생합니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println("나머지 결과  : " + num1.remainder(num2));
    }
}
 cs

public BigInteger pow(int exponent)

 this^exponent 값을 BigInteger로 return 해줍니다.

 지수값은 int 로 받아도 충분하므로 매개변수를 int 형 입니다.

1
2
3
4
5
6
7
8
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        System.out.println("제곱 결과  : " + num1.pow(2));
    }
}
 cs

public BigInteger gcd(BigInteger val)

 this 와 value 의 절댓값을 나누는 가장 큰 공약수를 BigInteger로 return 해줍니다. 만약에 this, val 가 모두 0이라면 gcd 값은 0이 됩니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println("최대공약수  : " + num1.gcd(num2));
    }
}
 cs

public BigInteger abs()

 this 의 절댓값을 BigInteger로 return 해줍니다.

1
2
3
4
5
6
7
8
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("-1823989474918578930411412385934");
        System.out.println("절댓값  : " + num1.abs());
    }
}
 cs

public BigInteger and(BigInteger val)

 this 와 val 값을 & (and) 연산해서 BigInteger 값으로 return 해줍니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println("num1 & num2  : " + num1.and(num2));
    }
}
 cs

public BigInteger or(BigInteger val)

 this 와 val 값을 | (or) 연산해서 BigInteger 값으로 return 해줍니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println("num1 | num2  : " + num1.or(num2));
    }
}
 cs

public BigInteger xor(BigInteger val)

 this 와 val 값을 ^ (xor) 연산해서 BigInteger 값으로 return 해줍니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("123456789123456789");
        System.out.println("num1 ^ num2  : " + num1.xor(num2));
    }
}
 cs

public BigInteger not(BigInteger val)

 val 값을 ~ (not) 연산해서 BigInteger 값으로 return 해줍니다.

1
2
3
4
5
6
7
8
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        System.out.println("~num1  : " + num1.not());
    }
}
 cs

public BigInteger min(BigInteger val)

 this 와 val 값 중 더 작은 값을 BigInteger 값으로 return 해줍니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("19847981358913892021");
        System.out.println("더 작은 값  : " + num1.min(num2));
    }
}
 cs

public BigInteger max(BigInteger val)

 this 와 val 값 중 더 큰 값을 BigInteger 값으로 return 해줍니다.

1
2
3
4
5
6
7
8
9
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        BigInteger num2 = new BigInteger("19847981358913892021");
        System.out.println("더 큰 값  : " + num1.max(num2));
    }
}
 cs

public String toString()

 BigInteger로 표현된 this 값을 String 으로 return 해줍니다.

1
2
3
4
5
6
7
8
import java.math.BigInteger;
 
public class test{
    public static void main(String args[]) {
        BigInteger num1 = new BigInteger("1823989474918578930411412385934");
        System.out.println("String으로 변환  : " + num1.toString());
    }
}
 cs

자바는 long 형을 벗어나는 정수를 다룰 수 있는 BigInteger 클래스와 다양한 메소드를 지원해줍니다.

이외에도 더 많은 메소드가 있지만, 오늘은 가장 유용하게 사용되는 메소드 위주로 정리를 해봤습니다.

 

'Computer Language > JAVA' 카테고리의 다른 글

[JAVA] #30 자바 컬렉션프레임워크(Collection Framework)  (0) 2020.07.03
[JAVA] #29 자바 제네릭, 제네릭클래스, 제네릭메소드  (0) 2020.06.26
[JAVA] #27 Integer 클래스 메소드 정리  (0) 2020.06.25
[JAVA] #26 자바 Number 클래스 메소드 정리  (0) 2020.06.23
[JAVA] #25 자바 Wrapper 클래스  (0) 2020.06.23

문제 : https://www.acmicpc.net/problem/18235

문제해석

 1 ~ N 까지 좌표들이 있고, 오리 두마리가 A 와 B 지점에서 시작해서 하루에 한 번 점프를 해가며 이동한다. 점프를 안하는 경우는 없고,  점프 크기는 1부터 시작해서 2배씩 늘어난다. 이때, 둘이 만날 수 있는지, 만난다면 몇 일이 지나고 만나는지를 구하는 프로그램을 작성하라.

문제핵심

 1. 점프 크기가 2배씩 늘어나므로 19일에 점프크기는 262,144(2^18)가 되고 N이 최대 500,000이므로 20일부터는 의미가 없어진다. 왜냐하면 20일 부터 점프 크기가 500,000보다 크므로 점프를 하면 어차피 범위를 벗어나게 된다. 따라서, 우리는 19일까지만 시뮬레이션을 진행해보면 된다. --> 19 * O(N) 으로 처리하자.

 2. 우리는 k 일에 A 오리와 B 오리가 갈 수 있는 모든 지점을 알고 있다면, (k + 1) 일에 A 오리와 B 오리가 갈 수 있는 모든 지점을 구할 수 있다. --> 모든 지점을 저장해가면서 진행해보자.

알고리즘

 문제핵심 1, 2번에 의해서 현재 A, B 오리가 도착한 지점을 통해 다음 A, B 오리가 도착한 지점을 저장해나가며 문제를 해결할 수 있다. 메모리를 조금이라도 아끼기위해 bool 배열과 flag 기법을 이용해서 저장해나갔다.

 day 0부터 시작해서 day가 짝수라면 visited[0] 에 현재 방문한 지점들이 있고, visited[1] 에 다음에 방문할 지점들을 check 해가며 문제를 해결했다.

 1) 현재 방문한 지점들 중에 겹치는 곳이 있는지. --> 있다면 오리가 만났다!

 2) 다음에 방문한 지점을 저장할 공간을 초기화한다.

 3) 현재 지점을 토대로 다음에 방문할 지점을 계산해 저장한다.

알고리즘회고

처음에는 2개의 deque를 이용해서 현재 A 오리가 갈 수 있는 모든 지점을 저장하고, B 오리가 갈 수 있는 모든 지점을 저장하고, deque의 앞에서부터 현재 지점들을 뽑아가며 jump 를 +, jump 를 - 해서 다음 지점들을 다시 deque의 뒤로 push 했다. 당연히 deque의 push, pop 이 굉장히 많이 일어났고, 현재 지점들에서 같은 지점이 있는지 없는지 체크를 위해 2개의 deque을 2중 for문으로 순회해야되서 시간초과를 맛보게 되었다. 따라서, 메모리를 조금 더 사용하고 deque을 사용하지 않는 방식으로 알고리즘을 갈아엎었다.

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
#include<iostream>
#include<qcueue>
#include<vector>
 
using namespace std;
int N, A, B, jump = 1, day = 0;
bool visitedA[2][500001] = {};
bool visitedB[2][500001] = {};
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    // 19일 안에 만나야됨!
 
    cin >> N >> A >> B;
 
    visitedA[0][A] = 1;
    visitedB[0][B] = 1;
    do {
        // day 가 짝수라면 visited[0] 에 기존것이있음!
        // day 가 홀수라면 visited[1] 에 기존것이있음!
        int today = day % 2;
        int nextDay = (today + 1) % 2;
        // 같은게 있는지 찾아보자.
        bool flag = false;
        for (int i = 1; i <= N; i++) {
            if (visitedA[today][i] && visitedB[today][i]) {
                flag = true;
                break;
            }
        }
        if (flag) {
            cout << day << '\n';
            break;
        }
 
        // 초기화 진행
        for (int i = 1; i <= N; i++){
            visitedA[nextDay][i] = 0;
            visitedB[nextDay][i] = 0;
        }
        for (int i = 1; i <= N; i++) {
            int nextJump1 = i + jump, nextJump2 = i - jump;
            if (visitedA[today][i]) {
                if (1 <= nextJump1 && nextJump1 <= N) visitedA[nextDay][nextJump1] = 1;
                if (1 <= nextJump2 && nextJump2 <= N) visitedA[nextDay][nextJump2] = 1;
            }
            if (visitedB[today][i]) {
                if (1 <= nextJump1 && nextJump1 <= N) visitedB[nextDay][nextJump1] = 1;
                if (1 <= nextJump2 && nextJump2 <= N) visitedB[nextDay][nextJump2] = 1;
            }
        }
        jump *= 2;
        day++;
    } while (jump <= 500000);
    if (jump > 500000) cout << -1;
    return 0;
}
 cs

 

'Problem Solving > BOJ' 카테고리의 다른 글

[BOJ] 3109 : PLINOVOD  (0) 2020.07.01
[BOJ] 15681 : 트리와 쿼리  (0) 2020.07.01
[BOJ]15591 : MooTube(Silver)  (0) 2020.06.22
[BOJ] 10021 : Watering the Fields  (0) 2020.06.22
[BOJ] 2352 : 반도체 설계  (0) 2020.06.15

+ Recent posts

티스토리툴바