초콜릿컵 실수들의 연속..ㅠㅜ

 

A번

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

31458번: !!초콜릿 중독 주의!!

코코의 초콜릿 가게에서 파는 초콜릿은 달달하기로 유명하다. 그래서 코코는 아래와 같은 경고문을 가게 앞에 붙이려고 한다.
"!!초콜릿 중독 주의!!" 이 문구를 유심히 보던 코코는 느낌표 사이의 문장을 지우고 그 자리에 수를 넣으면 일종의 수식이 된다는 사실을 깨달았다. 이 수식을 계산해 보자.
이 문제에서 계산할 수식은 정수 하나와 0개 이상의 느낌표로 이루어져 있다. 정수는 0 또는 1이며, 느낌표는 정수의 앞이나 뒤에 올 수 있다. 이 수식을 계산하는 규칙은 다음과 같다.
n!은 n의 팩도리얼이다. 1! = 1, 0! = 1로 정의된다.!n은 n!의 논리 반전(logical not)이다. !0 = 1, !1 = 0으로 정의된다.팩토리얼이나 논리 반전이 중첩되어 있으면 중첩된 횟수만큼 계산하며, !n!과 같이 둘 다 사용된 경우에는 팩토리얼을 먼저 계산한다. 예를 들어, !!n!!=!(!((n!)!))이다.

 

TimeLimit	MemoryLimit	조건	TAG
2s	1024MB	(1 ≤ T ≤ 1000; 0 ≤ a, b  ≤ 30; 0 ≤ n(정수) ≤ 1)	Implementation(구현)

 

문제에서 숫자(0 또는 1) 오른쪽이 먼저 처리된 후, 왼쪽이 처리된다. n!은 0이든 1이든 다 1로 만들기 때문에 오른쪽 !의 개수가 1 이상이면 무조건 1이 되기 때문에, 개수만 확인하고 넘어감. 그 후, 왼쪽의 논리 반전은 2번이면 다시 원상복구가 되기 때문에 2의 나머지가 1이면 !(not)을 취해주고 아니면 그대로 반환하여 정답을 찍어내는 방식을 사용함.

 

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    string inp;
    
    int t;
    cin >> t;
    
    while(t--){
        cin >> inp;
        bool state = false;
        int cnt[2] = {0, 0};
        bool current;
        
        for(char c : inp){
            if(c != '!'){ current = c - '0'; state = true;}
            else cnt[state]++;
        }
        
        
        if(cnt[1] > 0) current = 1;
        if(cnt[0] % 2) current = !current;

        cout << current << "\n";
    }
    
}

 

(너무나 간단한 코드, 간단한 로직이여서 넘어간다.)

 

 

 

B번

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

31460번: 초콜릿과 11과 팰린드롬

코코는 0부터 9까지의 숫자가 새겨진 초콜릿을 많이 갖고 있다. 코코는 이 초콜릿을 가지고 큰 수를 만들어서 한별이에게 선물하려고 한다.
코코는 한별이가 팰린드롬 수, 특히 11을 좋아한다는 사실을 알고 있기 때문에, 11의 배수인 팰린드롬 수를 만들고 싶다. 팰린드롬 수는 왼쪽에서 오른쪽으로 읽은 것과 오른쪽에서 왼쪽으로 읽은 것이 서로 같은 수를 말한다. 예를 들어, 9, 11, 4774, 13531은 팰린드롬 수이고, 1232, 1100은 팰린드롬 수가 아니다.
코코를 도와 11의 배수이면서 팰린드롬인 N자리의 음이 아닌 정수를 하나 찾아주자. 각 숫자가 새겨진 초콜릿은 충분히 많다고 가정한다. 0을 제외한 수는 숫자 0으로 시작할 수 없다.

 

TimeLimit	MemoryLimit	조건	TAG
2s	1024MB	(1 ≤ T ≤ 100; 1 ≤ N ≤ 10000)	Math(수학)

 

처음 문제를 봤을 땐 도대체 어떻게 저 큰 수들을 11의 배수이면서, 팰린드롬을 찾을까를 생각하다가 머리에 하나가 박혔다. 121, 1221,12221 이 수들이 지나가면서 11로 나누어 떨이지는 것이 머리에 딱 떠오른 것이 아닌가?! 그래서 잠시 얘기해보자면 11의 배수 판별은 홀수 자리의 합과 짝수 자리의 합의 차가 0이면 11의 배수임을 알 수 있다. 그러면 양 끝에 1을 두고서 안에 2로 채우면 되겠구나!가 되었다.

 

여기서 중요!! 11의 배수는 0도 포함되어 있다....(이거 몰라서 결국 못 품 ㅋㅋㅌ)

 

틀린 코드

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    int n;
    string result = "";
    while(t--){
        cin >> n;
        if(n == 1) result.append("-1");
        else{
            result.append("1");
            for(int i = 1; i < n-1; i++) result.append("2");
            result.append("1");
        }
        result.append("\n");
    }
    cout << result;
}

 

 

 

여기서 틀린 이유는 n이 1일 때 0이 나와야 하는데 -1을 출력해서 문제가 되었다.

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    int n;
    string result = "";
    while(t--){
        cin >> n;
        if(n == 1) result.append("0");
        else{
            result.append("1");
            for(int i = 1; i < n-1; i++) result.append("2");
            result.append("1");
        }
        result.append("\n");
    }
    cout << result;
}

 

이 코드로 AC를 맞았다.

 

 

 

C번

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

31459번: 초콜릿과 ㄱ나이트 게임 (Sweet)

 

코코는 가로 길이 X, 세로 길이 Y인 직사각형 모양의 초콜릿을 갖고 있다. 이 초콜릿은 1×1 크기의 단위 정사각형으로 나누어져 있다.
코코는 이 초콜릿과 여러 개의 ㄱ나이트를 가지고 ㄱ나이트 게임을 하려고 한다. ㄱ나이트는 체스에서 사용하는 나이트의 변형으로, 한 번에 오른쪽으로 x칸, 아래로 y칸 떨어진 칸으로 이동할 수 있다. ㄱ나이트는 이동할 때 다른 칸에 있는 말의 방해를 받지 않는다. 목적지 칸이 초콜릿의 범위를 벗어나는 경우에는 그곳으로 이동할 수 없다.
ㄱ나이트 게임은 초콜릿 위에 다음의 규칙을 지키면서 최대한 많은 ㄱ나이트를 올리는 게임이다.

1. 초콜릿의 한 칸에는 최대 하나의 ㄱ나이트를 올릴 수 있다.
2. 어떤 ㄱ나이트가 한 번에 이동할 수 있는 칸에 다른 ㄱ나이트가 있으면 안 된다.
3. 초콜릿은 뒤집거나 회전할 수 없다.

코코가 초콜릿에 ㄱ나이트를 최대 몇 개까지 올릴 수 있는지 계산해 보자.

 

TimeLimit	MemoryLimit	조건	TAG
2s	1024MB	(1 ≤ T ≤ 1000; 1 ≤ X, Y, x, y ≤ 50)	Greedy(탐욕법)

 

문제를 보자마자 일단 제일 이득인 경우는 내가 지금 둘 수 있을 때 바로 두는 것이 제일 좋은 수라는 것을 바로 알았다. 어떻게든 많이 둘 때 제일 많이 올릴 수 있기 때문에 말 그대로 왼쪽 상단에서부터 오른쪽 하단까지 쭉 탐색을 진행하면 될 것이라 생각하고, 바로 코드를 작성하였다.

 

bool board[51][51];
int rec(int currentx, int currenty, int result, int mx, int my, int n, int m){
    
    // printBoard(n, m);
    
    if(currentx >= m) return rec(0, currenty+1, result, mx, my, n, m);
    if(currenty >= n) return result;
    
    if(board[currenty][currentx]) return rec(currentx+1, currenty, result, mx, my, n, m);
    
    if(currentx+mx < m && currenty+my < n) board[currenty+my][currentx+mx] = true;
    int answer = rec(currentx+1, currenty, result+1, mx, my, n, m);
    
    return answer;
    
}
void solution(int n, int m, int mx, int my){
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            board[i][j] = false;
        }
    }
    cout << rec(0, 0, 0, mx, my, n, m) << "\n";
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    int t;
    int n, m, mx, my;
    cin >> t;
    while(t--){
        cin >> m >> n >> mx >> my;
        solution(n, m, mx, my);
    }
    
    
    return 0 ;
    
}

 

이렇게 코드를 작성하였다.

main에서는 테스트 케이스가 주어진 만큼 반복하여 실행하도록 하였고, 알고리즘을 돌리는 실질적 함수는 rec으로 재귀를 그대로 함수 이름으로 사용하였다. 

 

rec은 현재 위치 currenty, currentx에서 한번에 이동할 수 있는 위치에 board로 true로 바꿈으로서 다음에 방문했을 때 바로 넘어가도록 하여 못 두는 곳은 count하지 못하도록 하였다. 

 

시간 제한도 2초이고, 최대가 50*50이라 계산도 많이 걸리지 않았기 때문에 가뿐히 넘어간다.

 

하지만 나는... 입력을 받을 때 x, y를 반대로 입력받아서 왜 틀린지 몰라서 멘붕이 한번 왔었다.

다들 조심하셔요... 오타...ㅠㅜ

 

D번

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

31462번: 삼각 초콜릿 포장 (Sweet)

 

코코네 초콜릿 가게에서는 밸런타인데이 특별 상품으로 정육각형 3개를 삼각형 모양으로 붙인 초콜릿을 판매하려고 한다. 코코는 같은 크기의 정육각형 N(N+1)/2개를 삼각형 모양으로 붙인 형태의 틀에 이 초콜릿들을 빈틈없이 넣어 포장하려고 한다. 그리고 이를 조금 더 예뻐 보이게 하기 위해, 위로 뾰족한 방향으로 배치된 초콜릿은 빨간색, 반대 방향의 초콜릿은 파란색으로 개별 포장을 하기로 했다. 포장이 완료된 상품은 겉에서 볼 때 각각의 육각형이 빨간색인지 파란색인지만 알 수 있고, 어느 칸들이 같은 조각인지는 알 수 없다.

코코네 가게에 놀러 온 한별이는 완성된 상품을 구경하다가, 다른 모양의 초콜릿이 들어 있는 것으로 보이는 상품을 보게 되었다. 한별이를 도와서 주어진 상품이 잘못되었는지 판별하여 코코에게 알려주자.

 

TimeLimit	MemoryLimit	조건	TAG
2s	1024MB	(1 ≤ N ≤ 5000; 1 ≤ i ≤ N, 입력은 모두'R' 또는 'B'로 들어온다.)	Greedy(탐욕법)

 

이 문제는 R인지 B인지만 검사하면 돼서 딱히 어려운 문제는 아니었다. 이건 구현력만 받쳐준다면 금방 풀이할 수 있는 문제였기 때문에 딱히 풀이가 필요하지는 않다.

 

(아래서 말하는 정삼각형은 

                  R

                R  R

모양을 하고 있는 삼각형이고, 역정삼각형은

                B  B

                  B

의 모양을 하고있는 삼각혀이다.)

 

R는 정삼각형이 완성되면 되는 것이고, B는 역정삼각형이 완성되면 되는 것이다.(나는 여기서 어떻게든 삼각형을 만들어서 모양이 완성되면 되는 줄 알고서 문제를 풀었다가 망했다....ㅠㅜ)

 

그래서 검사를 할때 자신이 R이면 자기보다 깊이가 바로 아래있는 칸에 양 옆이 R이면 되고, B는 다음 앞에 B이고 그 아래에 B이면 완성되는 것이다. 이것을 검사하고 된다면 visited 처리를 한다면 알아서 탐색을 하면서 넘어갈 것이다.

 

이 로직을 그대로 구현한 코드는 바로 아래에서 보겠다.

 

string tri[5001];

bool visited[5001][5001];
int n;


bool solution(int current){
    if(current >= n-1) return true;
   // cout << tri[current] <<"\n";
    for(int i = 0; i < tri[current].size(); i++){
        
        if(visited[current][i] || visited[current][i]) continue;
         
        
        if(tri[current][i] == 'B'){
            //cout << (tri[current][i+1] == 'B') <<" "<< (tri[current+1][i+1] =='B') << "\n";
            if(i < tri[current].size() - 1 && tri[current][i+1] == 'B' && tri[current+1][i+1] =='B' && !visited[current+1][i+1]){
                visited[current+1][i+1] = true;
                i++;
            }else return false;
            
        }else if(tri[current][i] =='R'){
            //cout << (tri[current+1][i] =='R') <<" "<< (tri[current+1][i+1] =='R') << "\n";

            if(tri[current+1][i] =='R' && tri[current+1][i+1] =='R' && !visited[current+1][i] && !visited[current+1][i+1]){
                visited[current+1][i] = true;
                visited[current+1][i+1] = true;
            }else return false;
            
            
        }
        
    }
    
    
    return solution(current+1);
}
int main() {
    fast_io
    cin >> n;
    for(int i = 0; i <n ;i++) cin >> tri[i];
    if(n == 1) cout << 0;
    else cout << solution(0);
    return 0 ;
    
}

 

visited와 삼각형을 적절히 돌면서 정답을 알아냈다.