제5회 대학생 프로그래밍 경시대회 문제 A 장보기

2014-05-15

소스코드

public class Shopping {
    public static void main(String[] args) {
        /*int[][] order = {
                {300, 2000},
                {200, 1500}
        };*/
        /*int[][] order = {
                {320, 2139},
                {700, 3200},
                {1400, 6400}               
        };*/
        int[][] order = {
                {250, 1920},
                {500, 2980},
                {430, 2700},
                {380, 2350},
                {340, 2310}
        };
        System.out.println(choose(order));       
    }
    public static int choose(int[][] order) {
        // 1g 당 가격의 최소값
        long min = Long.MAX_VALUE;
        // 그 때의 원래 가격
        int cost = 0;
        for(int i = 0; i < order.length; i++) {
            // 현재 물건의 1g 당 가격
            long p = order[i][1] / order[i][0];
            // 기존의 물건 보다도 중량 대비 더 싸다면 가격을 저장한다.
            if(p < min) {
                min = p;
                cost = order[i][1];
            } else if(p == min) {    // 같다면 더 낮은 가격을 저장한다.
                if(order[i][1] < cost) {
                    cost = order[i][1];
                }
            }
        }
        return cost;       
    }   
}

주절주절

너무 옛날에 풀어서 정확히 기억이 안난다. 시간나면 다시 풀어보아야겠다.

제7회 대학생 프로그래밍 경시대회 문제 A Letter Bank

2014-05-14

ProgrammingAlgorithm

Algorithm, ICPC, Java, Programming

문제

문자 저장소는 새로운 단어를 만들기 위해 여러번(최소한 한번 이상) 사용된 모든 문자들로 구성된 단어이다. 예를들어 IMPS는 MISSISSIPPI의 문자 저장소이다. a 와 b의 두 단어를 입력으로 받고, 당신은 a가 b의 문자 저장소인지 판단하는 프로그램을 작성한다. 첫번째 단어가 (문자들이) 반복된 단어가 아니라고 가정해라. 모든 단어들은 오직 대문자들만 포함한다.(A, B, …, Z, 공백 없음)

입력

프로그램은 표준 입력으로부터 입력받는다. 입력은 T(1 ≤ T ≤ 20) 개의 테스트 조건을 갖는다. 테스트 조건의 개수인 T는 입력의 첫번째 줄에 주어진다. 각각의 테스트 조건들은 한줄에 두 단어가 주어진다. 첫번째 단어와 두번째 단어 사이에는 하나의 공백이 존재한다. 그리고 각 단어는 최대 80글자를 가진다.

출력

프로그램은 표준 출력으로 출력한다. 각 테스트 조건은 정확히 한줄에 하나씩 출력해라. 각 테스트 조건에 대해, 만약 첫번째 단어가 두번째 단어의 저장소이면 YES, 그렇지 않으면 NO를 출력해라.

소스코드

import java.util.Scanner;
public class LetterBank {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();    // 테스트 케이스 개수
        for(int i = 0; i < T; i++) {
            String a = scan.next();    // 첫번째 단어
            String b = scan.next();    // 두번째 단어
            process(a, b);
        }
    }
    public static void process(String bank, String word) {
        if(isBank(bank, word)) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }
    public static boolean isBank(String bank, String word) {
        boolean[] alpha = new boolean[26];
        // word에 나온 글자에 다 체크한다.
        for(int i = 0 ; i < word.length(); i++) {
            alpha[word.charAt(i) - 'A'] = true;
        }
        // bank의 글자에 체크 반전시킨다.
        for(int i = 0; i < bank.length(); i++) {
            alpha[bank.charAt(i) - 'A'] = !alpha[bank.charAt(i) - 'A'];
        }
        // 모두 처음의 값이면 성공한 것이다.
        for(int i = 0 ; i < alpha.length; i++) {
            if(alpha[i]) {
                return false;
            }
        }       
        return true;
    }
}

주절주절

중복한 문자들을 어떻게 처리할 수 있을까 생각하던중… 배열을 이용하기로 하였다. 괜찮은 판단이었던 것 같다. ㅋㅋ

제4회 대학생 프로그래밍 경시대회 문제 B 벌집

2014-05-14

ProgrammingAlgorithm

Algorithm, ICPC, Programming

Source Code

import java.util.Scanner;
public class Honeycomb {
    private static final int SIDE = 6;    // 벌집 면의 수
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();    // 테스트 케이스의 개수
        for(int i = 0; i < T; i++) {
            int N = scan.nextInt();    // 방 번호
            System.out.println(process(N));
        }       
    }
    public static int process(int N) {
        int d = 1;    // 지나가는 방의 개수
        int lev = 0;    // 각 레벨의 방의 개수
        while(N > 1) {
            lev += SIDE;
            N -= lev;
            d++;
        }
        return d;
    }
}

Comment

곰곰히 생각해보면 수열 문제로 생각할 수 있다. 벌집의 레벨이 늘어날때마다 각 레벨의 방의 개수가 6개씩 늘어난다. 중앙의 방에서부터 차례로 빼나가다보면 답이 나온다. 이 녀석은 나를 고민을 많이하게 만들었지만 재밌는 문제였다.

제4회 대학생 프로그래밍 경시대회 문제 A 점수 집계

2014-05-11

ProgrammingAlgorithm

Algorithm, ICPC, Java, Programming

소스코드

import java.util.Arrays;
import java.util.Scanner;
public class Score {
    private static final int NUM_REFEREE = 5;    // 심판의 수
    private static final int MAX_GAP = 4;    // 최고점과 최저점의 차이
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();    // 테스트 케이스 개수
        int[] N = new int[NUM_REFEREE];    // 다섯 심판이 준 점수
        for(int i = 0; i < T; i++) {
            for(int j = 0; j < N.length; j++) {
                N[j] = scan.nextInt();               
            }
            process(N);
        }
    }
    public static void process(int[] n) {
        // 정렬한다.
        Arrays.sort(n);
        // 최고점과 최저점을 제외한다.
        // 나머지 최고점과 최저점의 차이가 4점 이상 나면 KIN을 출력하고
        // 아니면 총점을 출력한다.
        if(Math.abs(n[1] - n[3]) >= MAX_GAP) {
            System.out.println("KIN");
        }
        else {
            System.out.println(n[1] + n[2] + n[3]);
        }
    }
}

주절주절

최소값과 최대값은 정렬을 하면 쉽게 구할 수 있다. 다행히 자바에서는 정렬 라이브러리가 있기에 쉽게 풀 수 있었다.

제9회 대학생 프로그래밍 경시대회 문제 E Maze

2014-05-11

ProgrammingAlgorithm

Algorithm, C++, ICPC, Programming

소스코드

#include <iostream>
#include <cmath>
using namespace std;
char** maze;    // 미로
int** usedEnergyMaze;    // 에너지 사용량
int M, N;    // 행, 열
// 재귀적으로 미로 전 영역의 에너지 사용량을 기록한다.
void GetUsedEnergy(int row, int col, int energy)
{
    // 미로 밖으로 벗어난 경우
    if(row < 0 || col < 0 || row >= M || col >= N)
    {
        return;
    }
    // 벽을 만나면 에너지 사용량을 증가시킨다.
    if(maze[row][col] == '*')
    {
        energy++;
    }
    // 알려진 에너지 사용량보다 적으면 갱신한다.
    if(energy < usedEnergyMaze[row][col])
    {
        usedEnergyMaze[row][col] = energy;
    }
    else
    {
        return;
    }
    // 네 방향으로 반복해서 탐색한다.
    GetUsedEnergy(row - 1, col, energy);
    GetUsedEnergy(row + 1, col, energy);
    GetUsedEnergy(row, col - 1, energy);
    GetUsedEnergy(row, col + 1, energy);
}
// 해당 에너지량으로 로봇을 구출할 수 있을지 판단한다.
bool canRescue(int energy)
{
    // 출발 위치를 구한다.
    int row, col;
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(maze[i][j] == 'S')
            {
                row = i;
                col = j;
            }
        }
    }
    // 미로 전 영역의 에너지 사용량을 구한다.
    GetUsedEnergy(row, col, 0);
    // 도착 위치까지의 에너지 사용량이 로봇의 에너지보다 작은지 판단한다.
    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(maze[i][j] == 'T')
            {
                if(usedEnergyMaze[i][j] <= energy)
                {
                    return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    int T;    // 테스트 케이스의 개수
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        int k;    // 로봇의 충전된 에너지
        cin >> k;
        cin >> M >> N;
        // 미로를 초기화한다.
        maze = new char*[M];
        for(int j = 0; j < M; j++)
        {
            maze[j] = new char[N];
        }
        for(int j = 0; j < M; j++)
        {
            for(int k = 0; k < N; k++)
            {
                cin >> maze[j][k];
            }
        }
        // 에너지 사용량을 초기화한다.
        usedEnergyMaze = new int*[M];
        for(int j = 0; j < M; j++)
        {
            usedEnergyMaze[j] = new int[N];
        }
        int intMax = pow(2, 31) - 1;    // 정수의 최대값
        for(int j = 0; j < M; j++)
        {
            for(int k = 0; k < N; k++)
            {
                usedEnergyMaze[j][k] = intMax;
            }
        }
        // 로봇을 구하면 y를 구하고, 아니면 n을 구한다
        if(canRescue(k))
        {
            cout << 'y' << endl;
        }
        else
        {
            cout << 'n' << endl;
        }
        // 메모리를 해제한다.
        for(int j = 0; j < M; j++)
        {
            delete[] usedEnergyMaze[j];
        }
        delete[] usedEnergyMaze;
        for(int j = 0; j < M; j++)
        {
            delete[] maze[j];
        }
        delete[] maze;
    }
    return 0;
}

주절주절

재귀적인 탐색 문제이다. 4방향으로 탐색하며 각 셀마다 이동하는데 사용되는 최소 에너지량을 구한다. 이미 방문한 셀이라도 더 적은 에너지로 갈 수 있으면 이동해야 한다.

제9회 대학생 프로그래밍 경시대회 문제 D 노선도

2014-05-11

ProgrammingAlgorithm

Algorithm, C++, ICPC, Programming

Source Code

#include <iostream>
using namespace std;
struct Station
{
    int x;
    int r;
};
bool IsGoodLine(Station* stations, int len)
{
    for(int j = 1; j < len - 1; j++)
    {
        int width = stations[j+1].x - stations[j-1].x;
        if(stations[j].r > width)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int T;  // 테스트 케이스의 개수
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        int N;
        cin >> N;
        Station* stations = new Station[N];
        for(int j = 0; j < N; j++)
        {
            cin >> stations[j].x >> stations[j].r;
        }
        if(IsGoodLine(stations, N))
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
        delete[] stations;
    }
    return 0;
}

Comment

생각보다 간단한 문제였네요.

키포인트는 해당 역의 이름표의 길이가 주변 역과의 거리보다 길면 안된다는 사실…

제3회 대학생 프로그래밍 경시대회 문제 A 수 뒤집기

2014-05-09

ProgrammingAlgorithm

Algorithm, ICPC, Programming

소스코드

import java.util.Scanner;
public class Reverse {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();// 테스트 케이스 개수
        for(int i = 0; i < T; i++) {
            int N = scan.nextInt();// 정수
            process(N);
        }
    }
    public static void process(int n) {
        // 원래 수와 뒤집은 수를 합한다.
        int sum = n + reverse(n);
        // 합한 수를 뒤집어 비교한다.
        if(sum == reverse(sum)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
    /**
    * 수를 뒤집는다. ex) 123 -> 321
    * 
    * @param num 뒤집을 수
    * @return 뒤집힌 수
    */
    public static int reverse(int num) {
        int ret = 0;
        while(num > 0) {
            // 기존 숫자를 왼쪽 시프트 한다.
            ret *= 10;
            // 마지막 한자리를 떼어낸다.
            double temp = num % 10;
            num /= 10;
            ret += temp;
        }
        return ret;
    }
}

주절주절

Palindrome(회문: 뒤집어도 같은 단어(ex: 별똥별)) 문제이다. 숫자를 문자열로 바꾸어서 처리해도 되지만, 문자로 바꾸지 않고 바로 뒤집어 보았다.

제2회 대학생 프로그래밍 온라인대회 문제 A 게시판

2014-05-09

ProgrammingAlgorithm

Algorithm, ICPC, Programming

소스코드

import java.util.Scanner;
public class Board {
    public static void main(String[] args) {       
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();    // 테스트 케이스의 개수
        for(int i = 0; i < T; i++) {
            int x1 = scan.nextInt();
            int y1 = scan.nextInt();
            int x2 = scan.nextInt();
            int y2 = scan.nextInt();
            int x3 = scan.nextInt();
            int y3 = scan.nextInt();
            int x4 = scan.nextInt();
            int y4 = scan.nextInt();
            process(x1, y1, x2, y2, x3, y3, x4, y4);           
        }      
    }
    public static void process(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
        int maxX = Math.max(x1, x3);
        //int maxX = x1 > x3 ? x1 : x3;
        int maxY = Math.max(y1, y3);
        //int maxY = y1 > y3 ? y1 : y3;
        int minX = Math.min(x2, x4);       
        // int minX = x2 < x4 ? x2 : x4;
        int minY = Math.min(y2, y4);       
        //int minY = y2 < y4 ? y2 : y4;
        int area = (x2 - x1) * (y2 - y1) - (minX - maxX) * (minY - maxY);
        System.out.println(area);
    }
}

주절주절

간단한 기하 문제이다. 먼저 붙힌 포스터의 넓이를 구한뒤 나중에 붙힌 포스터와 겹치는 넓이를 빼주면 된다.

ACM ICPC 2000 ASIA Problem A Car Racing

2014-05-06

ProgrammingAlgorithm

Algorithm, ICPC, Programming

Source Code

import java.util.Arrays;
import java.util.Scanner;
public class CarRacing {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt(); // 테스트 케이스의 개수
        for (int i = 0; i < T; i++) {
            int N = scan.nextInt(); // 자동차의 개수
            int[] cars = new int[N]; // 자동차 번호 배열
            for (int j = 0; j < N; j++) {
                cars[j] = scan.nextInt();
            }
            process(cars);
        }
    }
    public static void process(int[] cars) {
        // 바로 들어갈 수 있는 차들은 보내고 나머지만 남긴다.
        int i = 0;       
        while(cars[i] == (i + 1)) {
            i++;
        }
        cars = Arrays.copyOfRange(cars, i, cars.length);
        // 다음으로 들어가야할 차의 위치를 구한다.       
        int index = getIndexOfMinValue(cars);
        // 그 녀석보다 앞의 차들은 바이패스로...
        // 그 녀석보다 뒤의 차들은 원래 라인으로...       
        int[] bypass = Arrays.copyOfRange(cars, i, index);
        int[] original = Arrays.copyOfRange(cars, index + 1, cars.length);
        // 두 라인에서 순서대로 들어갈 수 있으면 YES
        // 아니라면 NO를 출력한다.
        if (isSorted(bypass) && isSorted(original)) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }
    /**
        * 배열에서 최소값의 위치를 구한다.
        * @param numbers 배열
        * @return 최소값의 위치
        */
    public static int getIndexOfMinValue(int[] numbers) {
        int min = numbers[0];
        int index = 0;
        for (int i = 1; i < numbers.length; i++) {
            if (numbers[i] < min) {
                min = numbers[i];
                index = i;
            }
        }
        return index;
    }
    /**
        * 오름차순으로 정렬되어 있는지 판단한다.
        * @param numbers 정수 배열
        * @return 오름차순으로 정렬되어 있으면 YES, 아니면 NO
        */
    public static boolean isSorted(int[] numbers) {
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

Comment

문제를 잘못 이해해 bypass에 차가 한 대만 들어간다고 생각해버렸다. 다시 수정하여 풀었다. 정렬을 이용하여 풀어보았다. 하지만 Queue를 이용해서 풀면 좋을 듯한 문제인듯 ㅋㅋ

ACM ICPC 2000 ASIA Practice Problem B Cross a Creek

2014-05-06

ProgrammingAlgorithm

Algorithm, ICPC, Programming

Source Code

import java.util.Scanner;
public class CrossCreek{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);       
        int t = scan.nextInt();    // 테스트 케이스 개수
        for(int i = 0; i < t; i++) {
            int n = scan.nextInt();    // 개울의 너비
            process(n);
        }
    }
    public static void process(int n) {
        // 모든 경우를 구한다.
        long sum = 0;
        for(long i = n, r = 0; i >= r; i--, r++){
            sum += combination(i, r);
        }
        System.out.println(sum);
    }
    // 팩토리얼을 구한다.
    // n! = n * (n-1) * (n-2) * ... * 2 * 1
    // ex) 4! = 4 * 3 * 2 * 1 = 24
    public static long factorial(long n){
        if(n <= 1){
            return 1;
        }
        return n * factorial(n - 1);
    }
    // 조합을 구한다.
    // nCr = nPr / r! = n! / ((n-r)! * r!)
    // ex) 4개 중에 2개를 고르는 경우의 수 = 6가지
    public static long combination(long n, long r){
        return factorial(n) / (factorial(n - r) * factorial(r));
    }
}

Comment

문제를 보고 고민을 하다가 조합으로도 풀 수 있단것을 알게되었다. 수학책을 찾아보고 조합 공식에 맞춰 함수를 작성하였다.