Program Artist를 꿈꾸는 Blog

문제

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다.
• 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다. 

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

전체 코드(Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        int ans = 0;
        int size = 0;

        for (int i = 0; i < s.length() - 1; i++) {
            char c = s.charAt(i);
            char n = s.charAt(i+1);

            if ('(' == c && ')' == n) {
                ans += size;
                i++;
                continue;
            }

            if ('(' == c) {
                ans++;
                size++;
            } else if (')' == c) {
                size--;
            }
        }

        System.out.println(ans);
    }
}

풀이

1. 처음에는 예제의 입력과 출력을 살펴보며 규칙성을 찾고자 하였다.

1) 레이저가 나올 때 그 앞의 '(' 개수 만큼 쇠 막대기의 총 개수가 증가한다는 것을 알았다

2) 막대를 자를 때 추가되는 개수와 기존 막대의 개수를 고려하여 여는 괄호가 등장할 때 마다 총 합의 개수를 1씩 늘려줘야 한다

- 쇠막대를 한 번 자르면 기존 1개의 막대 + 추가 1개의 막대로 생각할 수 있다

- 이 상태에서 한 번 더 자르면 기존 2개의 막대 + 추가 1개의 막대로 생각할 수 있다

  - 레이저는 '(' 다음 ')'이 나오게 되므로, 매 루프 시 현재 인덱스의 문자와 다음 인덱스의 문자를 검사하여 레이저를 처리하였다.

  - 이 부분은 ')'가 등장할 때 예외 처리를 통해 심플하게 구성할 수 있을 듯 하다.

- s.length() - 1 까지 for 루프를 도는 이유는, 어차피 마지막은 닫는 괄호로 끝날 것이기 때문이다. 마지막 닫는 괄호는 결과에 영향을 주지 않는다.

2. 규칙성을 찾은 다음에는 스택 자료구조를 사용하면 간단하게 해결될 것으로 보였다.

- 하지만 코드를 구상하면서 스택의 사이즈만을 사용하는 것을 깨닫게 되어 굳이 스택을 구현하지는 않았다.

- 대신 현재의 여는 괄호 개수를 기록할 변수인 'size'를 이용하였다

3. 상기의 규칙성에 따라 기본적인 문법 만을 이용하여 구현하였다. 

진법 변환

• 다른 진법 => 10진수
  • Integer.parseInt(문자열, 문자열의 진수)
  • ex) System.out.println(Integer.parseInt("A", 16))
    • 출력 : 10
• 10진수 => 16진수
  • Integer.toHexString(10진수 정수)
    • 16진수로 변환된 문자열을 반환
    • ex) String s = Integer.toHexString(15)
      • s에 "f"가 저장됨
      • 대문자로 변환하고 싶다면 Integer.toHexString(15).toUpperCase()를 이용
  • Integer.toBinaryString / Integer.toOctalString 등 여러 진수에 대한 변환 제공

import에 관해서

• ArrayList는 java.util.ArrayList 필요
• Arrays는 java.util.Arrays 필요
• StringTokenizer는 java.util.StringTokenizer 필요
• Scanner는 java.uitl.Scanner
• 처음에 import java.util.*;로 임포트하면 대부분 사용 가능
• Buffered 세트는 java.io.*;로 임포트하면 쉽게 사용 가능
• 따라서 코딩 테스트에서는 import java.util.* + java.io* 조합으로 대다수의 메소드와 클래스를 이용가능

Arrays.asList 사용

• List list = new ArrayList(Arrays.asList(arr));
  • 주의 : List list = Arrays.asList(arr);와 같이 사용하면 정적 클래스를 리턴함(사이즈를 바꾸지 못함)
    • 원본 배열의 주소값을 가져옴
    • 내가 사용하는 java.util.ArrayList와 달리 이렇게 생성된 것은 java.util.Arrays.ArrayList 클래스임
      • 따라서 set(), get(), contains() 등의 메서드만 있음
    • 이 경우 새로운 원소 추가 및 삭제가 불가능
      • add나 remove를 실행해보니 오류가 뜸

String.join

• List 또는 Array에 대해서 각 인덱스를 구분하는 구분자를 추가하여 반환(return 자료형은 String)
• List / Array의 자료형은 String형이어야 함
  • ex) System.out.println(String.join("+", arr))
    • arr(또는 list) : {1, 2, 3, 4, 5, 6, 7, 8}
    • 실행 결과 : 1+2+3+4+5+6+7+8
    • 마지막 인덱스에는 구분자가 붙지 않음
    • String s = String.join(" ", list)와 같이도 사용 가능

ArrayList

• import java.util.ArrayList가 필요
• ArrayList<타입> numbers = new ArrayList<>()로 생성
• 주요 메소드
  • add(타입 e) : 원소 추가
    • add(int index, 타입 e) : 원하는 인덱스에 원소 추가
  • clear() : 모든 원소 제거
  • clone() : 리스트 복제
  • contains(Object o) : 객체가 있는지 확인. 있으면 true, 없으면 false 반환
  • get(int index) : index에 해당하는 원소를 반환
  • indexOf(Object o) : o에 해당하는 원소가 있는 인덱스를 반환
  • isEmpty() : 원소가 없으면 true, 하나라도 있으면 false
  • remove(int index) : index에 해당하는 인덱스의 원소를 삭제
  • remove(Integer.valueOf(숫자)) : 숫자에 해당하는 원소를 삭제
  • set(int index, E element) : index에 해당하는 원소를 element로 교체
  • size() : 원소의 개수를 반환
  • Collections.sort(ArrayList) : ArrayList를 오름차 순으로 정렬
  • Collections.sort(ArrayList, Collections.reverseOrder()) : list를 역순(내림차순)으로 정렬
  • Collections.sort(ArrayList, Comparator) : ArrayList를 원하는 규칙으로 정렬
    • @Override를 통해 public int compare(E a, E b)를 재정의 해야 함
    • return 값이 음수 : a < b
    • return 값이 양수 : a > b
    • return 값이 0 : a = b
    • a - b와 같이 return 할 수도 있지만, 이 경우에 a - b 값이 오버플로우를 일으키면 잘못된 정렬이 이루어질 수 있음
      • 따라서 a.compareTo(b);와 같이 사용하는 것이 좋음
      • Integer 등 wrapper 클래스는 compareTo 메소드를 제공
      • 역순 정렬 시에는 b.compareTo(a);
    • 규칙을 정해서 정렬 가능(같은 나이는 이름 기준으로 오름차순 등) 
    • // 람다 표현식을 사용하여 ArrayList을 역순으로 정렬 Collections.sort(list, (Integer a, Integer b) -> -(a - b));
    • // ArrayList을 역순(내림차 순)으로 정렬 Collections.sort(list, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return b.compareTo(a); } });

Arrays 클래스

• import java.util.Arrays 필요
• Arrays.asList(배열) : 배열을 리스트로 바꿈
  • List list = new ArrayList(Arrays.asList(arr));
  • 이와 같이 사용해야함.
• Arrays.binarySearch(배열, 찾는 값) : 정렬되어 있는 상태에서 찾는 값의 인덱스를 반환
  • 찾는 값이 없으면 음수를 반환
  • 찾는 값이 배열에서 어디 위치하느냐에 따라 다른 음수값 반환
  • 예를 들어 배열이 {1, 5, 9}라고 하고, 찾는 값이 4면 -2를 반환
    • X 1 X X X 5 X X X 9
    • 4, 10, 16를 기준으로 찾는 값이 K일 때
    • K < 4 : -1 반환
    • 4 < K < 10 : -2 반환
    • 10 < K < 16 : -3 반환
    • K > 16 : -4 반환
• Arrays.sort(배열) : 배열을 오름차순 정렬
• Arrays.sort(배열, Collections.reverseOrder())
  • 배열을 역순으로 정렬
  • 이 때, 배열은 "Wrapper Class"여야 함
    • ex : int [] arr (X. 기본 타입) , Integer [] arr (O. 래퍼 클래스)
• Arrays.sort(배열, Comparator) : 배열을 규칙을 정해서 정렬
  • Collections.sort랑 동일
  • *Collections.sort는 "ArrayList"에 사용하고 Arrays.sort는 일반 배열에 사용
  • @Override를 통해 public int compare(E a, E b)를 재정의 해야 함
  • return 값이 음수 : a < b
  • return 값이 양수 : a > b
  • return 값이 0 : a = b
  • a - b와 같이 return 할 수도 있지만, 이 경우에 a - b 값이 오버플로우를 일으키면 잘못된 정렬이 이루어질 수 있음
    • 따라서 a.compareTo(b);와 같이 사용하는 것이 좋음
    • Integer 등 wrapper 클래스는 compareTo 메소드를 제공
    • 역순 정렬 시에는 b.compareTo(a);
  • 규칙을 정해서 정렬 가능(같은 나이는 이름 기준으로 오름차순 등)

    // 람다 표현식을 사용하여 배열을 역순으로 정렬
    Arrays.sort(arr, (Integer a, Integer b) -> -(a - b));
    

    // 람다 Comparator 사용 : 이름 순으로 오름차순 정렬하되, 같은 이름은 나이 내림차순 정렬
    Arrays.sort(pl, (Person a, Person b) -> {
    	if (a.getName() == b.getName()) {
    		return -(a.getAge() - b.getAge());
    	}
    	return a.getName().compareTo(b.getName(;
    });
    

  • // 배열을 역순(내림차 순)으로 정렬 Arrays.sort(arr, new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return b.compareTo(a); } });
• Arrays.fill(배열, 값) : 해당 배열을 값으로 채움
• Arrays.copyOf(배열, 복사할 길이) : 복사할 길이 만큼 배열을 복사하여 반환
  • 사용법
  • int [] arr2 = Arrays.copyOf(arr, 5);
  • arr[0] ~ arr[5-1] 까지 복사
• Arrays.copyOfRange(배열, 시작 인덱스, 마지막 인덱스) : 시작 인덱스 ~ (마지막 인덱스 - 1)까지 복사

String 클래스

• 기본적으로 변경이 불가능한 immutable 객체
• 주요 메소드
  • str1.equals(String str2) : str1과 str2를 비교해서 같으면 true 다르면 false
  • str.split(String regex) : 패러미터로 전달된 특정 문자열 또는 정규 표현식을 기준으로 String을 나누어 배열로 리턴함
  • str.length() : 문자열 str의 길이 반환
    • cf. 배열 타입의 길이는 arr.length
  • str.replace(”대상 문자열”, “바꿀 문자열”)
    • ex) str = str.replace(”123”, “456”)
      • String은 immutable함. String.replace() 메소드는 해당 스트링을 변환하는 것이 아닌 변환된 문자열을 리턴함
    • replaceAll() 과의 차이는 정규표현식
      • replaceAll()은 정규표현식을 사용할 수 있음
      • 따라서 replaceAll()은 일반적인 특수문자를 사용하기 어려움
      • 이러한 이유로 replace()를 사용하는 것이 편할 것으로 보임
  • str.charAt(int index) :index에 해당하는 char 형 원소를 반환
    • 자바에서는 문자열의 인덱스 접근이 안되기 때문에, charAt으로 인덱스 접근을 수행
  • str.substring(int 시작 인덱스, int 끝 인덱스) : 시작 인덱스 ~ (끝 인덱스 - 1)까지의 문자열을 리턴
    • 끝 인덱스를 생략하면 첫번째 인자부터 문자열 끝까지 리턴
    • substring으로 특정 인덱스 제거한 문자열 반환받기
      • str = str.substring(0, 제거할 인덱스) + str.substring(제거할 인덱스 + 1);
    • substring으로 특정 인덱스 문자열 치환
      • str = str.substring(0, 치환할 인덱스) + (치환할 인덱스 문자열) + str.substring(치환할 인덱스 + 1);
  • (static) String.valueOf(객체) : 객체를 문자열로 반환
    • String.valueOf(객체)에서 객체 자리에 정수, BigInteger 등 여러 가지가 들어갈 수 있음
  • (static) Integer.parseInt(String str) : Integer 클래스의 정적 메소드로 str을 정수로 변환함
  • str1.contains(String str2) : str2이 포함되어있는지 확인하여 있으면 true 아니면 false
  • str1.indexOf(String str2) : str2이 시작되는 인덱스를 리턴하고, 해당 str2이 존재하지 않으면 -1을 리턴
  • str.toUpperCase() : 문자열을 전체 대문자로 새로운 객체 반환
  • str.toLowerCase() : 문자열을 전체 소문자로 새로운 객체 반환
  • str1.compareTo(str2) : str1과 str2를 비교하여 정수 리턴
    • return 값이 음수 : str1 < str2(str2이 사전순으로 뒤에 등장)
    • return 값이 양수 : str1 > str2(str2이 사전순으로 앞에 등장)
    • return 값이 0 : str1 = str2
  • (static) String.format("%d + %d", 1, 2) : 포맷에 맞춘 문자열 반환
    • 위의 예시는 "1 + 2" 반환
  • str.repeat(int count) : str을 count번 만큼 반복하여 리턴
    • JDK 11 이상부터 지원

Character 클래스

• Character.isDigit(char ch)
  • ch가 숫자라면 true, 아니라면 false를 리턴
• Character.isLetter(char ch)
  • ch가 문자라면 true, 아니라면 false를 리턴
  • Character.isAlphabetic(char ch)와 거의 동일하며, 코딩테스트 수준에서는 같다고 봐도 될듯
  • isLetter()가 좀 더 기억하기 쉽고 짧으니 이를 사용하도록 하자
• Character.toUpperCase(char ch)
  • ch를 대문자로 변경
• Character.toLowerCase(char ch)
  • ch를 소문자로 변경

StringBuilder 클래스

• import java.lang.StringBuilder가 필요(기본적으로 가능)
• 주요 메소드
  • [ String 클래스와 동일 메소드 ]
• charAt(int index) : index 위치의 char형 원소 반환
  • indexOf(String str) : 문자열에서 해당 문자열이 처음 시작되는 인덱스를 반환
  • length() : 문자열 길이를 정수로 반환
  • replace() : 검색된 문자열 교체
  • substring(int 시작 인덱스, int 끝 인덱스) : 시작 인덱스 ~ (끝 인덱스 - 1)까지의 문자열을 리턴
    • 끝 인덱스를 설정하지 않으면 첫번째 인자부터 문자열 끝까지 리턴
  • toString() : 문자열 출력
  • 고유 메소드
    • append(String str) : 기존 문자열에 인자 문자열 추가
    • delete(int 시작 인덱스, int 끝 인덱스) : 시작 인덱스 ~ (끝 인덱스 - 1)까지의 문자열을 삭제
    • deleteCharAt(int index) : index의 원소 삭제
    • insert(int index, String str) : 해당 index 위치에 str을 삽입
    • reverse() : 문자열을 거꾸로 뒤집음
    • setCharAt(int index, char c) : index의 문자를 c로 변경

Deque 자료구조 : 스택과 큐 구현 가능

• 참고 : https://hbase.tistory.com/128
• import java.util.*로 사용 가능
• 스택의 구현 : BOJ 10828 / 큐의 구현 : BOJ 10845 / 덱의 구현 : BOJ 10866
• 사용 : Deque deque = new ArrayDeque<>();
• 값 추가 함수
  • 덱의 앞쪽에 데이터 삽입
    • offerFirst() : 덱의 앞쪽에 데이터 삽입 후 true 반환, 용량 초과시 false 반환
    • addFirst() / push() : 덱의 앞쪽에 데이터 삽입. 용량 초과시 예외 발생
  • 덱의 뒷쪽에 데이터 삽입
    • offerLast() / offer() : 덱의 뒷쪽에 데이터 삽입 후 true 반환. 용량 초과시 false 반환
    • addLast() / add() : 덱의 뒷쪽에 데이터 삽입, 용량 초과시 예외 발생
    • 참고 : addLast()가 offerLast()보다 빠름(아마 offerLast는 반환이 있어서 그렇지 않을까 추측)
• 값 제거 함수
  • 덱의 앞쪽의 데이터 제거
    • pollFirst() / poll() : 덱의 앞쪽의 데이터를 제거 및 반환. 덱이 비어있으면 null 리턴
    • removeFirst() / remove() / pop() : 덱의 앞쪽의 데이터 삭제. 덱이 비어있으면 예외 발생
  • 덱의 뒷쪽의 데이터 제거
    • pollLast() : 덱의 뒷쪽의 데이터 제거 및 반환. 덱이 비어있으면 null 리턴
    • removeLast() : 덱의 뒷쪽의 데이터 제거 및 반환. 덱이 비어있으면 예외 발생
  • 특정 객체 제거
    • remove(Object o) : 덱의 앞쪽부터 시작하여, 일치하는 첫번째 객체를 제거 후 true 반환
      • 존재하지 않을 시 false 반환
• 값 체크 함수
  • 덱의 첫번째 원소 확인
    • peekFirst() / peek() : 덱의 맨 앞(첫번째 원소)를 확인. 비어있으면 null 반환
    • getFirst() : 덱의 맨 앞(첫번째 원소)를 확인. 비어있으면 예외 발생
  • 덱의 마지막 원소 확인StringTokenizer는 레거시 클래스로, String.split을 사용하는 것이 더 좋음(공식 문서)
    • peekLast() : 덱의 맨 뒤(마지막 원소)를 확인. 비어있으면 null 반환
    • getLast() : 덱의 맨 뒤(마지막 원소)를 확인. 비어있으면 예외 발행
  • 덱에 특정 객체가 있는지 확인
    • contains(Object o) :
  • 덱의 원소의 개수
    • size() : 덱의 원소의 개수를 반환
• 정리 : 스택과 큐 구현 시 First, Last 둘 중 어떤걸 사용할 것인가
  • 기본적으로 스택은 후입 선출(LIFO), 큐는 선입 선출(FIFO)의 원칙만 지키면 됨
    • Deque의 메소드를 종합하여 보면 데이터의 제거 연산은 First 쪽에서 된다고 생각하면 됨
      • Stack 연산
        • push() = addFirst()
        • pop() = removeFirst()
      • Queue 연산
        • add() = addLast()
        • remove() = removeFirst()
    • 스택의 경우 removeFirst()와 addFirst()를 사용하여 구현하면 됨
      • First에서 제거, First에서 삽입 -> 후입 선출(LIFO)
    • 큐의 경우 removeFirst()와 addLast()를 사용하여 구현하면 됨
      • First에서 제거, Last에서 삽입 -> 선입 선출(FIFO)

BigInteger

• import java.math.BigInteger가 필요
• BigInteger = new BigInteger(String)으로 생성
• 주요 메소드
  • BigInteger.add(BigInteger) : 덧셈, 반환 타입 BigInteger
  • BigInteger.subtract(BigInteger) : 뺄셈, 반환 타입 BigInteger
  • BigInteger.multiply(BigInteger) : 곱셈, 반환 타입 BigInteger
  • BigInteger.divide(BigInteger) : 나눗셈, 반환 타입 BigInteger
  • BigInteger.remainder(BigInteger) : 나머지, 반환 타입 BigInteger
• String str = String.valueOf(BigInteger)로 문자열 변환 가능

Scanner 클래스

• import java.uitl.Scanner 필요
• Scanner sc = new Scanner(System.in)으로 객체 생성
• 주요 메소드
  • sc.nextLine() : 문자열 한 줄 입력
  • sc.next() : 문자열을 공백 또는 줄바꿈까지 읽음
  • sc.nextInt() : 정수를 입력받음
    • 1 2 3 이렇게 한 줄로 입력시 nextInt()를 3개 소모함
    • 예를 들어 int a = sc.nextInt(); int b = sc.nextInt(); int c = sc.nextInt(); 일 때
    • 1 2 3 입력하면 a = 1, b = 2, c = 3이 들어감
• 마지막에 sc.close()로 닫는 것을 잊지 말기

BufferedReader && BufferedWriter

• import java.io.* 하는 것이 마음 편함
• BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
• 다음과 같이 사용하며,BufferedReader 또는 BufferedWriter 사용시에는 main에 throws IOException을 추가해야 함
• public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int a = Integer.parseInt(br.readLine()); System.out.println(a); } }
• 주요 메소드(BufferedReader)
  • readLine() : 한 줄의 문자열을 읽음
  • 사용이 끝난 후 br.close()를 해주어야 함
  • 공백 기준으로 구분하기 위해 StringTokenizer가 필요
• 주요 메소드(BufferedWriter)
  • write(문자열) : 문자나 문자열을 버퍼에 씀
    • 정수를 출력할 땐 String.valueOf(정수) 식으로 만들어서 출력해야 함
    • 버퍼에 넣는 방식이므로, 출력 값이 버퍼 사이즈보다 작으면 flush()를 통해 출력해야 함
    • 말 그대로 버퍼에 write하는 함수이므로, 출력 결과는 flush()를 통해 비워내지 않으면 마지막에 한 번에 출력됨
  • newLine() : 빈 줄을 작성(개행)
  • flush() : 버퍼를 모두 비워냄. 일부 문제에서 bw.write() 다음에 bw.flush()를 해주어야 하는 경우가 있음
  • close() : 사용이 끝난 후 close()를 해줌
• 출력이 아주 많은 경우가 아니라면, BufferedWriter는 사용하지 않는 것이 편함

※ 코딩테스트를 준비하며 개인적으로 공부하고 경험한 것을 기록하기 위한 목적으로 작성한 문서이며, 정확하지 않은 내용이 포함되어 있을 수 있습니다.

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

제한

• 1 ≤ k, n ≤ 14

전체 코드(Java)

import java.io.*;

public class Main {
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        int k, n;
        int[][] arr = new int[15][15];

        for (int i = 0; i < 15; i++) {
            arr[0][i] = i;
            arr[i][0] = 0;
        }

        for (int i = 1; i < 15; i++) {
            for (int j = 1; j < 15; j++) {
                arr[i][j] = arr[i-1][j] + arr[i][j-1];
            }
        }

        for (int i = 0; i < T; i++) {
            k = Integer.parseInt(br.readLine());
            n = Integer.parseInt(br.readLine());
            bw.write(String.valueOf(arr[k][n]));
            bw.newLine();
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

풀이

• 규칙을 파악하기 위해 아파트의 층과 호수를 2차원 배열로 생각한다
  • 메모장에 그려보며 규칙을 파악한다
  • arr[i][j] = arr[i-1][j] + arr[i][j-1]이라는 규칙성을 발견한다
• 0번째 줄에 대한 처리를 한다(첫번째 for문)
• 찾아낸 규칙으로 2차원 배열의 나머지 부분을 채운다
• 입력받은 k와 n으로 2차원 배열을 인덱스 접근하여 값을 출력한다

문제

땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.

달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.

달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)

출력

첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다.

전체 코드(Java)

import java.io.*;
import java.util.StringTokenizer;
public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        double A = Integer.parseInt(st.nextToken());
        double B = Integer.parseInt(st.nextToken());
        double C = Integer.parseInt(st.nextToken());

        int ans = (int)Math.ceil((C - A) / (A - B)) + 1;

        bw.write(String.valueOf(ans));

        bw.flush();
        bw.close();
        br.close();
    }
}

풀이

• 달팽이가 나무 막대를 모두 올라가는 시간을 공식화 하였다.
  • while 문으로 구할 수도 있지만, 시간이 많이 소요될 것으로 예상
  • 달팽이는 아침에 A만큼 올라가고 밤에는 B만큼 내려가므로 올라갈 거리인 C를 A-B로 나누면 된다는 생각을 할 수 있다
  • 하지만, 저것만으로는 항상 하루 단위로 생각한 것이다. 실제로는 아침에 올라가기 때문에 목표 거리에 도달하면 밤에 다시 내려가는 것을 계산하지 않아야 한다
    • 예를 들어 하루에 2 만큼 올라가고 1 만큼 내려가는데 목표 거리가 2라면 1일 아침에 도착한다. 그러나 C / (A-B)라는 공식으로는 2라는 답이 나오므로 틀린 답이다.
    • 이를 막기 위해 반올림 메소드인 ceil을 이용했다.
    • (int)Math.ceil((C - A) / (A - B)) + 1 공식에 의하면 아침에 도달하는 경우를 포함해 정확히 계산이 가능하다

문제

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

이와 같이 나열된 분수들을 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

출력

첫째 줄에 분수를 출력한다.

전체 코드(Java)

import java.io.*;

public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int A = 1;
        int B = 1;
        boolean flag = true;
        int X = Integer.parseInt(br.readLine());
        int count = 1;

        while (count != X) {
            if (flag == true) {
                if (A == 1) {
                    B++;
                    flag = false;
                    count++;
                }
                else {
                    A++;
                    flag = false;
                    count++;
                }
            }
            else {
                if (A == 1) {
                    for (; B != 1 && count != X; A++, B--) {
                        count++;
                    }
                    flag = true;
                }
                else {
                    for (; A != 1 && count != X; A--, B++) {
                        count++;
                    }
                    flag = true;
                }
            }
        }

        bw.write(String.valueOf(A + "/" + B));

        bw.flush();
        bw.close();
        br.close();
    }
}

풀이

1. X가 1일 때 "1/1"이 출력되므로, A,B의 초기값을 1/1로 설정
2. 이동 패턴 분석
   • 좌표가 지그 재그 형태로 움직임
   • A/B로 나타냈을 때 A 또는 B가 변화할 때 마다 1번 움직인 것으로 측정
   • (a) 대각선으로 이동 => (b) A가 1일 때 B+1 / (c) B가 1일 때 A+1 => (a)대각선으로 이동의 패턴 반복
     • 초기 값인 1/1일 때는 패턴 (b)인 B+1로 시작
   • flag라는 boolean 변수를 이용해서 "(a)" 또는 "(b), (c)로 움직여야 하는 경우"를 결정
     • flag가 true일 때는 (b) 또는 (c)로 움직여야 하는 상황, (b)와 (c)는 A, B 중 어떤 것이 1인가에 따라 결정
     • flag가 false일 때는 (a)로 움직여야 할 상황, 대각선으로 이동하며 A/B 중 어떤 것이 1인가에 따라 방향 결정
       • A가 1이라면 A는 1씩 더하고, B는 1씩 빼서 B가 1이 되거나 count가 목표한 횟수가 될 때 까지 반복소감

• 생각할 시간이 필요한 문제였음
• 소요 시간이 204ms로 상위권 제출자의 시간인 128~140ms에 비하면 느리다고 할 수 있음
  • 최적화 할 수 있는 방법이 존재
• 본 코드는 if else 문을 이용해 모든 이동 패턴을 (그나마) 직관적으로 알 수 있다는 점에서 장점이 있다고 생각
  • 모든 행동 패턴은 크게 4가지로 분류됨. (a) 패턴은 A가 증가하고 B가 감소하는 (a-1) 패턴과 B가 증가하고 A가 감소하는 (a-2) 패턴으로 나눌 수 있으며 총 (a-1), (a-2), (b), (c)로 모든 패턴이 나눠진다고 할 수 있음