[코드포스 CODEFORCES] 1538A Stone Game 풀이 코드 (C/C++/Java /Python)

코드포스(Codeforces) 1538A Stone Game 풀이 코드

C | C++ | Java | Python

Difficulty : *800 (Brute force / DP / Greedy)

---

문제 해설

폴리카프는 새로운 게임을 하고 있습니다. 주어진 수열의 가장 큰 수와 가장 작은 수를 가장 적은 횟수 내로 없애는 게임입니다. 가장 작은 수는 1로 고정이고 가장 큰 수는 수열의 크기와 같습니다. 한 번에 한 숫자만 없앨 수 있으며, 없앨 수 있는 숫자는 매번 수열 양 끝의 숫자 뿐입니다.

풀이

가장 작은 수(1)와 가장 큰 수(수열의 크기)의 위치를 알아낸 후, 두 지점을 기준으로 수열을 나눌 때 생기는 세 거리를 각각 구합니다. 이 세 거리 중 짧은 순으로 두 개를 합하는 것이 정답입니다.

코드

• C
• C++
• Java
• Python

#include <stdio.h>

int main(){
    int n, m, i, j, maxslot, minslot, mid, dis1, dis2, dis3, result, arr[101];
    for(i = 0; i<101;i++){
        arr[i] = 0;
    }
    scanf("%d", &n);
    
    //find min and max
    for(i = 0; i < n; i++){
        scanf("%d", &m);
        for(j = 0; j < m; j++){
            scanf("%d", &arr[j]);
            if(arr[j]==m){
                maxslot = j;
            }
            if(arr[j]==1){
                minslot = j;
            }
        }
        mid = j/2;
        
        //get distance
        if(minslot<maxslot){
            dis1 = minslot + 1;
            dis2 = maxslot - minslot;
            dis3 = j-maxslot;
        }
        else{
            dis1 = maxslot + 1;
            dis2 = minslot - maxslot;
            dis3 = j-minslot;
        }
        
        //get shortest distance
        if(dis1<=dis2&&dis1<=dis3){
            if(dis2<dis3){
                result = dis1 + dis2;
            }
            else{result = dis1 + dis3;}
        }
        else if(dis2<=dis1&&dis2<=dis3){
            if(dis1<dis3){
                result = dis1 + dis2;
            }
            else{result = dis2 + dis3;}
        }
        else if(dis3<=dis1&&dis3<=dis2){
            if(dis1<dis2){
                result = dis1 + dis3;
            }
            else{result = dis2 + dis3;}
        }

        printf("%d\n", result);
        for(j = 0; j < 101; j++){
            arr[j] = 0;
        }
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n, m, maxslot, minslot, mid, dis1, dis2, dis3, result, arr[101], dist_list[3];
    for(int i = 0; i < 101; i++){
        arr[i] = 0;
    }
    cin>>n;
    
    //find min and max
    for(int i = 0; i < n; i++){
        cin>>m;
        for(int j = 0; j < m; j++){
            cin>>arr[j];
            if(arr[j]==m){
                maxslot = j;
            }
            if(arr[j]==1){
                minslot = j;
            }
        }
        mid = m/2;
        
        //get distance
        if(minslot<maxslot){
            dis1 = minslot + 1;
            dis2 = maxslot - minslot;
            dis3 = m-maxslot;
        }
        else{
            dis1 = maxslot + 1;
            dis2 = minslot - maxslot;
            dis3 = m-minslot;
        }
        
        //get shortest distance
        dist_list[0] = dis1, dist_list[1] = dis2, dist_list[2] = dis3;
        sort(dist_list, dist_list+3); 
        result = dist_list[0] + dist_list[1];

        cout<<result<<endl;
        for(int j = 0; j < 101; j++){
            arr[j] = 0;
        }
    }
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        int maxslot = 0, minslot = 0, dis1, dis2, dis3, result;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        //find min and max
        for(int i = 0; i < n; i++){
            int m = sc.nextInt();
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j < m; j++){
                int a = sc.nextInt();
                list.add(a);
                if(a == m){
                    maxslot = j;
                }
                if(a == 1){
                    minslot = j;
                }  
            }
            
            //get distance
            if(minslot<maxslot){
                dis1 = minslot + 1;
                dis2 = maxslot - minslot;
                dis3 = m-maxslot;
            }
            else{
                dis1 = maxslot + 1;
                dis2 = minslot - maxslot;
                dis3 = m-minslot;
            }
            
            //get shortest distance
            List<Integer> dist_list = new ArrayList<>();
            dist_list.add(dis1);
            dist_list.add(dis2);
            dist_list.add(dis3);
            Collections.sort(dist_list);
            result = dist_list.get(0) + dist_list.get(1);
            
            System.out.println(result);
        }
    }
}

n = int (input ()) 
arr =[] 

#find min and max
for i in range(n):
    m = int(input())
    arr = list(map(int, input().split()))
    for j in range(m):
        if arr[j] == m:
            maxslot = j    
        if arr[j] == 1:
            minslot = j 
    mid = m / 2
    
    #get distance
    if minslot < maxslot:
        dis1 = minslot + 1
        dis2 = maxslot - minslot
        dis3 = m - maxslot
    else:
        dis1 = maxslot + 1
        dis2 = minslot - maxslot
        dis3 = m - minslot
 
    #get shortest distance
    dist_list = [dis1, dis2, dis3]
    dist_list = sorted(dist_list)
    result = dist_list[0] + dist_list[1]

    print(result)

문제 출처

https://codeforces.com/contest/1538/problem/A