2026-03-08 문제풀이

오늘은 주말에 푼 두 문제를 정리했다.

7682 틱택토

풀이

노가다를 하면 되는데 꽤나 경우가 많다.
일단 선공이 이기는 경우와 후공이 이기는 경우를 잘 생각해야하는데

• 후공이 이길 경우 판에 놓여진 돌의 개수가 똑같다.
• 선공이 이길 경우 판에 놓여진 돌의 개수는 선공(X)이 하나 더 많다.

그리고 모든 경우 돌의 개수 차이는 1개 이하로 난다. (물론 선공이 더 많은 쪽으로)

돌의 개수가 1개 이하로 난다면,
두 줄을 쌩으로 일자로 만들 수는 없다.(6개의 돌을 쓰는 셈이니까) 따라서 3개 이상의 줄은 절대 안나온다.
승리 패턴이 하나 보인다면 나머지 사람은 승리할 수 없다.
이런 상황들을 정리하면 아래와 같다.

1. 보드가 선공 5, 후공 4이면 일단 성공한다고 보자. (승리 패턴이 이상하게 나오면 안되는걸로 바뀔 수 있음)
2. 세로, 가로, 대각선을 보면서 선공이 이기는 패턴과 후공이 이기는 패턴을 센다. (패턴이 나오면 일단 가능한 보드라고 생각해두자)
3. 놓여진 돌의 개수차이가 1이하가 아니면 실패한다.
4. 후공이 2줄 이상 만드는건 불가능하다 (5개의 돌이 필요하기 때문)
5. 선공이 승리패턴을 만들고 후공도 만드는건 불가능하다.
6. 선공이 이겼는데 (돌이 하나 많은데) 후공이 승리패턴이 생기는건 불가능하다
7. 후공이 이겼는데 (돌이 같은데) 선공이 승리패턴이 생기는건 불가능하다.

이걸 적용한게 아래 코드다.

코드

while 1 : 
    s = input()
    if s == 'end' : break

    ok = 0
    oc, xc = s.count('O'),s.count('X')
    D = {}
    D['O'], D['X'] = 0, 0
    # 꽉차서 끝난경우
    if  oc == 4 and xc == 5 : 
        ok = 1

    # 세로 확인
    for i in range(3) : 
        if s[i] == s[i+3] == s[i+6] and s[i] != '.' : 
            ok = 1
            D[s[i]] += 1
            
    
    # 가로 확인
    for i in range(3) : 
        if s[i*3] == s[3*i+1] == s[3*i+2] and s[3*i] != '.' :
            ok = 1
            D[s[3*i]] += 1
    
    # 대각선 확인
    if (s[0] == s[4] == s[8] and s[0] != '.') : 
        ok = 1
        D[s[4]] += 1
    if (s[2] == s[4] == s[6] and s[2] != '.') :
        ok = 1
        D[s[4]] += 1
    
    # 개수 안맞음
    if xc - oc > 1 or  xc -oc < 0: 
        ok = 0
    # print(D)
    if D['O'] > 1 or (D['O'] == 1 and D['X'] == 1) or (xc > oc and D['O'] > 0) or (xc == oc and D['X'] > 0):
        ok = 0

    print("valid" if ok else "invalid")
     

35296 아침 점호

풀이

점호를 대신 맞길 수 있는 학생은 나를 기준으로 위 아래 사람이다.
두 칸짜리를 최대한 많이 만드는게 중요하다. 가로로는 어짜피 못만들고 세로는 계속 만들 수 있으면 만들면 된다.
다만 주의해야 할 점은 예제 3이다.
가로가 한 칸 밖에 없으면 바로 옆을 커버할 수 있다는 점이다.
이를 예외로 구현하면 된다.
예제 3이 없었다면 놓칠만 했던 문제였다.

코드

#include <bits/stdc++.h>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlll;
#define xx first
#define yy second


int main(){
    fast_io
    int n, m; cin >> n >> m;
    vector<string> G(n);
    vector<vector<int>> R;
    for(int i=0;i<n;i++) cin >> G[i];
    if(n == 1){
        for(int j=0;j<m;j++){
            if(G[0][j] == 'X'){
                vector<int> K;
                K.push_back(1+j);
                if(j+1<m&&G[0][j+1] == 'X'){
                    K.push_back(2+j);
                    j += 1;
                }
                R.emplace_back(K);
            }
        }
    }else{
        for(int j=0;j<m;j++){
            for(int i=0;i<n;i++){
                if(G[i][j] == 'X'){
                    vector<int> K;
                    G[i][j] = 'O';
                    K.push_back(i + 1 + n * j);
                    if(i+1<n && G[i+1][j] =='X'){
                        G[i+1][j] = 'O';    
                        K.push_back(i+2 + n*j);
                    }
                    R.emplace_back(K);
                }
            }
        }
    }

    
    cout << R.size() << '\n';
    for(auto v : R){
        cout << v.size() << ' '; 
        for(auto x : v) cout << x << ' ';
        cout << '\n';
    }
}