BLOG :||

5. 뉴스 클러스터링(난이도: 중)

여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다.

개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 “카카오 신입 개발자 공채” 관련 기사를 검색해보았다.

• 카카오 첫 공채..’블라인드’ 방식 채용
• 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용
• 카카오, 블라인드 전형으로 신입 개발자 공채
• 카카오 공채, 신입 개발자 코딩 능력만 본다
• 카카오, 신입 공채.. “코딩 실력만 본다”
• 카카오 “코딩 능력만으로 2018 신입 개발자 뽑는다”

기사의 제목을 기준으로 “블라인드 전형”에 주목하는 기사와 “코딩 테스트”에 주목하는 기사로 나뉘는 걸 발견했다. 튜브는 이들을 각각 묶어서 보여주면 카카오 공채 관련 기사를 찾아보는 사용자에게 유용할 듯싶었다.

유사한 기사를 묶는 기준을 정하기 위해서 논문과 자료를 조사하던 튜브는 “자카드 유사도”라는 방법을 찾아냈다.

자카드 유사도는 집합 간의 유사도를 검사하는 여러 방법 중의 하나로 알려져 있다. 두 집합 A, B 사이의 자카드 유사도 J(A, B)는 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값으로 정의된다.

예를 들어 집합 A = {1, 2, 3}, 집합 B = {2, 3, 4}라고 할 때, 교집합 A ∩ B = {2, 3}, 합집합 A ∪ B = {1, 2, 3, 4}이 되므로, 집합 A, B 사이의 자카드 유사도 J(A, B) = 2/4 = 0.5가 된다. 집합 A와 집합 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으니 따로 J(A, B) = 1로 정의한다.

자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장할 수 있다. 다중집합 A는 원소 “1”을 3개 가지고 있고, 다중집합 B는 원소 “1”을 5개 가지고 있다고 하자. 이 다중집합의 교집합 A ∩ B는 원소 “1”을 min(3, 5)인 3개, 합집합 A ∪ B는 원소 “1”을 max(3, 5)인 5개 가지게 된다. 다중집합 A = {1, 1, 2, 2, 3}, 다중집합 B = {1, 2, 2, 4, 5}라고 하면, 교집합 A ∩ B = {1, 2, 2}, 합집합 A ∪ B = {1, 1, 2, 2, 3, 4, 5}가 되므로, 자카드 유사도 J(A, B) = 3/7, 약 0.42가 된다.

이를 이용하여 문자열 사이의 유사도를 계산하는데 이용할 수 있다. 문자열 “FRANCE”와 “FRENCH”가 주어졌을 때, 이를 두 글자씩 끊어서 다중집합을 만들 수 있다. 각각 {FR, RA, AN, NC, CE}, {FR, RE, EN, NC, CH}가 되며, 교집합은 {FR, NC}, 합집합은 {FR, RA, AN, NC, CE, RE, EN, CH}가 되므로, 두 문자열 사이의 자카드 유사도 J("FRANCE", "FRENCH") = 2/8 = 0.25가 된다.

입력 형식

• 입력으로는 str1과 str2의 두 문자열이 들어온다. 각 문자열의 길이는 2 이상, 1,000 이하이다.
• 입력으로 들어온 문자열은 두 글자씩 끊어서 다중집합의 원소로 만든다. 이때 영문자로 된 글자 쌍만 유효하고, 기타 공백이나 숫자, 특수 문자가 들어있는 경우는 그 글자 쌍을 버린다. 예를 들어 “ab+”가 입력으로 들어오면, “ab”만 다중집합의 원소로 삼고, “b+”는 버린다.
• 다중집합 원소 사이를 비교할 때, 대문자와 소문자의 차이는 무시한다. “AB”와 “Ab”, “ab”는 같은 원소로 취급한다.

출력 형식

입력으로 들어온 두 문자열의 자카드 유사도를 출력한다. 유사도 값은 0에서 1 사이의 실수이므로, 이를 다루기 쉽도록 65536을 곱한 후에 소수점 아래를 버리고 정수부만 출력한다.

예제 입출력

문제 해설

이 문제는 자카드 유사도를 설명해주고 자카드 유사도를 직접 계산하는 프로그램을 작성하는 문제입니다. 자카드 유사도는 실무에서도 유사한 문서를 판별할 때 주로 쓰이는데요, 몰랐더라도 문제에서 자세히 설명해주기 때문에 이해하는데 어려움은 없었을 거 같습니다. 공식은 매우 간단한데요, 교집합을 합집합으로 나눈 수입니다. 다만, 이 값은 0에서 1 사이의 실수가 되는데, 여기서는 이를 다루기 쉽도록 65536을 곱한 후 소수점 아래를 버리고 정수부만 취하도록 합니다.

문제 설명은 원소의 중복을 허용하는 다중집합^multiset으로 되어 있는데, 자주 접하는 자료구조가 아니고, 일부 언어에서는 기본으로 제공하는 자료구조가 아니라 어려워하는 분들이 있었습니다. 하지만 다중집합 자료구조를 쓰지 않더라도, 각 원소를 정렬된 배열에 넣은 후 병합 정렬^{Merge sort}에서 배웠던 코드를 응용, 어렵지 않게 합집합과 교집합 함수를 직접 구현할 수도 있습니다.

다중집합의 교집합, 합집합만 잘 구해낸다면 이 문제는 어렵지 않게 풀 수 있으며, 다만 집합 A와 B가 모두 공집합일 경우에는 나눗셈이 정의되지 않으므로^{division by zero} 따로 J(A,B) = 1로 정의합니다. 즉, 65536을 곱하면 이 경우 1 * 65536 = 65536이 정답이 됩니다. 예제 입출력에도 합집합이 공집합인 경우가 포함되어 있으므로 이 경우만 주의한다면 쉽게 풀 수 있는 문제입니다.

이 문제의 정답률은 41.84%입니다.

{1, 2, 2} 형태의 집합이라도 중복을 허용한다는게 첫 주의점이고 위의 문제 해설대로 각 집합의 개수가 0개일 경우를 설정하는 것이 두 번째 주의점이다.

그 외에는 딱히 어려운 점이 없는 것 같다. 그래서 4번 문제보다 정답률이 높았던 것으로 보인다.

package kakao02;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Vector;

public class kakao02 {

    static int Answer;

    public static void main(String args[]) throws Exception {

        Scanner sc = new Scanner(System.in);
        int n1 = Solution("FRANCE", "french");
        int n2 = Solution("handshake","shake hands");
        int n3 = Solution("aa1+aa2","AAAA12");
        int n4 = Solution("E=M*C^2","e=m*c^2");
        System.out.println(n1);
        System.out.println(n2);
        System.out.println(n3);
        System.out.println(n4);

    }
    public static int Solution(String str1, String str2)
    {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        Vector<String> str1Sub = new Vector<String>();
        Vector<String> str2Sub = new Vector<String>();
        int str1SetCount;
        int str2SetCount;
        int sub;
        for(int i = 0; i<str1.length()-1;++i)
        {
           
            if(str1.charAt(i) < 65 || str1.charAt(i) > 90)
            {
                continue;
            }
            else if(str1.charAt(i+1) < 65 || str1.charAt(i+1)>90)
            {
                i++;
                continue;
            }
            str1Sub.add(str1.substring(i, i+2));
        }
       
        for(int i = 0; i<str2.length()-1;++i)
        {
            if(str2.charAt(i) < 65 || str2.charAt(i) > 90)
            {
                continue;
            }
            else if(str2.charAt(i+1) < 65 || str2.charAt(i+1)>90)
            {
                i++;
                continue;
            }
            str2Sub.add(str2.substring(i, i+2));
        }
        str1SetCount = str1Sub.size();
        str2SetCount = str2Sub.size();
        str1Sub.retainAll(str2Sub);
       
        sub = str1Sub.size();
        int parent = str1SetCount + str2SetCount - sub;
        System.out.println(parent);
        float result = (float)sub/(str1SetCount + str2SetCount - sub);
        if(parent == 0)
            result = 1;
        return (int)(result*65536);
    }
}

4. 셔틀버스(난이도: 중)

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 ‘크루’라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

입출력 예제

문제 해설

쉬워 보이는데 어려운 문제가 바로 이 문제였던 거 같네요. 당초 난이도를 ‘중’으로 두고 문제를 중간 즈음에 배치하였는데, 시간을 계산하는 부분에서 많은 분들이 어려워하셨던 거 같습니다.

예를 들어 2번 입출력 예제의 경우 ["09:10", "09:09", "08:00"]인데 이 경우 두 번째 버스는 9:10분에 출발하기 때문에 9:10분에 오면 되지 않느냐 많이들 혼동하셨을 거 같아요. 하지만 9:00에 오는 버스는 8:00에 대기하는 크루 1명만 탑승할 수 있고, 따라서 9:10 버스에는 남아 있는 두 명이 모두 타게 됩니다. 따라서 좀 더 이른 9:09에 와야 탑승할 수 있습니다.

전체 계산은 어렵지 않지만 이처럼 정확하게 시간 계산을 해야 하는 부분이 많고 마지막 버스 시간까지 빈틈없이 계산해야 해서 많은 분들이 실수를 한 거 같습니다. 이 문제는 정답률이 두 번째로 낮은 26.79%입니다.

난이도 중 문제임에도 정답률이 낮다. 실제로 풀어보니 시간이 많이 걸렸다. 도중에 다른 문제로 교체한 사람들이 있어서 그런 듯 하다.

모든 크루들의 시간을 분으로 변경한다는 것은 처음부터 정해져 있던 내용이고 그 이후의 행동이 중요한데

vector나 list를 자동 정렬해주거나 removeif 메소드를 지원하는게 장점인 것 같다. C++은 포기하고 자바만 파두는게 나을지도 모르겠다.

콘은 무조건 막차만 타야 하기 때문에 앞 차량에 태울 수 있는 경우 모두 태워서 보내야 한다.

막차 시간 이후에 오는 사람은 고려할 필요가 없기 때문에 모두 보내버리면 된다.

그 후엔 막차 버스를 기준으로 허용량을 넘는가 아닌가만 고려하면 시간은 걸리지만 어려운 문제는 아니었다.

package kakao02;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;
import java.util.List;

public class kakao02 {

	public static void main(String[] args) {
		String a = Solution(1, 1, 5, new String[] { "08:00", "08:01", "08:02", "08:03" });
		String b = Solution(2, 10, 2, new String[] { "09:10", "09:09", "08:00" });
		String c = Solution(2, 1, 2, new String[] { "09:00", "09:00", "09:00", "09:00" });
		String d = Solution(1, 1, 5, new String[] { "00:01", "00:01", "00:01", "00:01", "00:01" });
		String e = Solution(1, 1, 1, new String[] { "23:59" });
		String f = Solution(10, 60, 45, new String[] { "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59",
				"23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59" });
		System.out.println(a);
		System.out.println(b);
		System.out.println(c);
		System.out.println(d);
		System.out.println(e);
		System.out.println(f);
	}

	public static String Solution(int n, int t, int m, String[] timetable) {

		Vector<Integer> time = new Vector<Integer>();
		for (int i = 0; i < timetable.length; ++i) {// 크루들의 도착 시간을 int 형태로 Vector에 저장
			String[] temp = timetable[i].split(":");
			time.add(Integer.parseInt(temp[0]) * 60 + Integer.parseInt(temp[1]));
		}
		Collections.sort(time);// 도착 시간을 오름차순으로 정렬

		Vector<Integer> busTime = new Vector<Integer>();// 버스의 도착 시간을 저장하기 위한 배열
		busTime.add(540);// 첫 시작은 540 == "09:00"
		for (int i = 1; i < n; ++i) {// 운행 횟수만큼 추가된 시간이 더해진 운행시간 값을 저장.
			busTime.add(540 + t * i);
		}
		int lastBusTime = busTime.get(busTime.size() - 1);// 버스 막차 시간 확인

		time.removeIf(i -> i > lastBusTime);// 막차시간 이후에 오는 크루는 고려할 필요 없음. 예제6

		if (n > 1) {
			for (int i = 0; i < busTime.size() - 1; ++i) {// 콘은 막차를 타야 한다. 그 이전에 태울 수 있는 사람은 모두 삭제.
				for (int j = 0; j < m; ++j) {
					if (time.size() != 0)
						if (busTime.get(i) >= time.get(0)) {
							time.remove(0);
						}
				}
			}
		}

		if (m <= time.size())// 남은 인원수가 막차 허용량보다 많은 경우
		{
			for (int i = 0; i < m; ++i) {
				if (lastBusTime >= time.get(0)) {
					if (i < m - 1) {// 막차 허용량 안에 들어갈 경우 앞 사람부터 삭제
						time.remove(0);
					} else {//크루가 버스에 탈 수 있는데 마지막 허용량일 경우
						int lastBusHour = time.get(0) / 60;//해당 크루의 시간을 받아오고
						
						int lastBusMin = (time.get(0) % 60);//해당 크루의 분을 받아온 후에, -1분 해준다.
						if (lastBusMin == 0) {
							lastBusMin = 59;
							lastBusHour -= 1;
						} else
							lastBusMin--;
						
						String timeText = String.format("%02d", lastBusHour);//String이 아니라 int를 입력해야 한다.
						timeText += ":";
						timeText += String.format("%02d", lastBusMin);
						return timeText;
					}
				} else if (i < m) {//허용량이 남았지만 더이상 크루들이 타지 못하는 경우. 위에서 removeif를 했기에 쓸 일은 없다.
					//마지막 버스 시간에 도착하면 된다.
					int lastBusHour = lastBusTime / 60;
					int lastBusMin = lastBusTime % 60;
					String timeText = String.format("%02d", lastBusHour);
					timeText += ":";
					timeText += String.format("%02d", lastBusMin);
					return timeText;
				}
			}
		} else// 남은 인원수가 막차 허용량보다 적은 경우. 마지막 버스 도착 시간에 맞춰서 타면 된다.
		{
			int lastBusHour = lastBusTime / 60;
			int lastBusMin = lastBusTime % 60;
			String timeText = String.format("%02d", lastBusHour);
			timeText += ":";
			timeText += String.format("%02d", lastBusMin);
			return timeText;
		}
		return null;

	}
}

3. 캐시(난이도: 하)

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, “총 실행시간”을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

입출력 예제

package kakao02;

import java.util.Scanner;
public class kakao02 {

	public static void main(String[] args)
	{
		String[] arr = new String[]{"Jeju", "Pangyo", "Seoul","NewYork", "LA", "Jeju","Pangyo", "Seoul", "NewYork", "LA"};
		String[] arr2 = new String[] {"Jeju", "Pangyo", "Seoul", "NewYork", "LA"};
		System.out.println(Solution(arr2));
	}
	public static int Solution(String[] cities)
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//cacheSize = new int[t];
		int time = 0;
		int bufferCount = 0;
		String[] cacheSize = new String[n];
		int[] cacheNum = new int[n];
		
		for(int i = 0; i<cities.length;++i)
		{
			boolean check = false;
			for(int j = 0; j<n;++j)
			{
				if(cities[i].toUpperCase().equals(cacheSize[j]))
				{
					time++;
					check = true;
					cacheNum[j] = i;
					break;
				}
			}
			if(!check) {			
				if(bufferCount < n) {
					cacheSize[bufferCount] = cities[i].toUpperCase();
					cacheNum[bufferCount] = i;
					bufferCount++;
				}
				else
				{
					int lastNum = 1000000;
					int count = -1;
					for(int j = 0; j < n;++j)
					{
						if(lastNum > cacheNum[j])
						{
							lastNum = cacheNum[j];
							count = j;
						}
					}
					if(n != 0)
					{
					cacheNum[count] = i;
					cacheSize[count] = cities[i].toUpperCase();
					}
				}
				time+=5;
			}
		}
		
		
		return time;
	}
}

2. 다트 게임(난이도: 하)

카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.
갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수^1 , 점수^2 , 점수^3 )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

“점수|보너스|[옵션]”으로 이루어진 문자열 3세트.
예) 1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.
예) 37

입출력 예제

문제 해설

문제에서 토큰화를 이용해서 풀라고 했는데 단어 단위로 문제를 풀었다. 한 번 푼 내용은 보존하고 다시 풀어야 할 것 같다.

단어 단위로 끊을 경우엔 별 어려움이 없다. 각 글자가 특수기호인지 아닌지를 구분하여 숫자를 넘겨주고, 그대로 활용하면 된다. 문제점이라면 java를 안쓴지 오래되서 입력법도 해깔렸다.

문자열 문제 다루는 것에는 C++보다 Java가 쉽더라.

package kakao02;

import java.util.Scanner;
public class kakao02 {

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		String dart;
		dart = sc.next();
		int arr[] = new int[3];
		int result = 0;
		int count = 0;
		String tempNum ="";
		for(int i = 0; i<dart.length();++i)
		{
			if(dart.charAt(i) =='S')
			{
				arr[count] = Integer.parseInt(tempNum);
				tempNum = "";
				arr[count] = (int)Math.pow(arr[count], 1);
				count++;
			}
			else if(dart.charAt(i)=='D')
			{
				arr[count] = Integer.parseInt(tempNum);
				tempNum = "";
				arr[count] = (int)Math.pow(arr[count], 2);
				count++;
			}
			else if(dart.charAt(i)=='T')
			{
				arr[count] = Integer.parseInt(tempNum);
				tempNum = "";
				arr[count] = (int)Math.pow(arr[count], 3);
				count++;
			}
			else if(dart.charAt(i)=='*')
			{
				if(count==1)
				{
					arr[count-1] *=2;
				}
				else
				{
					arr[count-2]*=2;
					arr[count-1]*=2;
				}
			}
			else if(dart.charAt(i)=='#')
			{
				arr[count-1]*= -1;
			}
			else
			{
				tempNum+=dart.charAt(i);
			}
		}
		result = arr[0] + arr[1]+arr[2];
		System.out.println(result);
	}
}

4
1 5 6 7

10

5
10 9 8 7 6

50

10
1 1 2 3 5 8 13 21 34 55

55

10
5 10 11 12 13 30 35 40 45 47

50

4
5 2 8 10

20

4
3 5 15 16

18

다이나믹 프로그래밍 문제라고 친구에게 받았지만 앞서 풀었던 문제들과 느낌이 달라서 당황스러웠다.

생각한 과정은 처음에 n 개당 얼마라는 가격이 정해져 있는데,

만약 2개를 파는 가격이 2개 가격보다 1개씩 두 개 파는 경우가 더 비싼 경우, 해당 숫자는 필요없게 된다.

P2의 존재가 의미 없어지고 P1 + P1이 P2의 가격을 대체하게 된다. 이를 MaxPrice[개수]로 별도 저장한다.

그런 식으로 쭉 각 개수에 대한 최대값을 기록하다보면 

MaxPrice[n]의 값을 구하기 편해진다. MaxPrice[n] = MaxPrice[n-i] + MaxPrice[i]( 0<= i <= n/2)가 된다.

3개 이상을 더해서 MaxPrice[n]을 구할 수 있지 않나 생각할 수 있는데 3개 이상의 항이 있을 때, 모든 항을 더해야 n의 개수와 같아지기 때문에 모두 MaxPrice가 존재한다. 따라서 두개의 항 밖에 존재하지 않는다.

#include <iostream>
#include <stdio.h>
using namespace std;
int price[1001] = {0};
int maxprice[1001] = {0};
int checkMaxPrice(int n)
{
      if(n == 1)
      {
          maxprice[n] = price[n];
          return maxprice[n];
      }
    else if(maxprice[n] != 0)
    {
        return maxprice[n];
    }
    else
    {
        int max = price[n];
        for(int i = 1; i<= n/2;++i)
        {
        	if(max < checkMaxPrice(i) + checkMaxPrice(n-i))
        		max = checkMaxPrice(i) + checkMaxPrice(n-i);
        }
        return maxprice[n] = max;
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i = 1; i<=n;++i)
    {
        cin>>price[i];
    } 
    int max = checkMaxPrice(n);
    cout << max;
    return 0;
}

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제 입력 1

3

예제 출력 1

2

학교에서 한번도 다이나믹 프로그래밍에 대한 이야기를 들어본 적이 없었다. 학교 커리큘럼에 안타까움을 느낀다.

인터넷의 다른 답안에서는 피보나치를 이야기 하는데, 피보나치 여부를 문제 풀 당시에는 인지하지 못했고, 

끝자리가 1이냐 0이냐에 따라 변화는 관계를 이용하여 문제를 풀었다. 

n-1 자리에서 끝자리가 0인게 x 개이고 1인게 y 개일 때, n 자리의 끝자리가 0인 이친수의 개수는 x+y 개이고, 

1인 이친수의 개수는 x 개이다. 라는 내용을 기반으로 문제를 풀었다.

int는 안되고, unsigned int도 안되고 long long을 해야 되는 개수에 놀랐다.

#include <iostream>
#include <stdio.h>

using namespace std;

struct Pinary
{
	long long oneT = 0;
	long long zeroT = 0;
	//unsigned int oneP = 0;
	//unsigned int zeroP = 0;
};
Pinary pinaryArray[90];


Pinary PinaryCheck(int n)
{
	if (n <= 1)
	{
		pinaryArray[n - 1].zeroT = 0;
		pinaryArray[n - 1].oneT = 1;
		return pinaryArray[n - 1];
	}
	else if (pinaryArray[n - 1].zeroT != 0 || pinaryArray[n - 1].oneT != 0)
	{
		return pinaryArray[n - 1];
	}
	else
	{
		Pinary t = PinaryCheck(n - 1);
		pinaryArray[n - 1].zeroT = t.zeroT + t.oneT;
		pinaryArray[n - 1].oneT = t.zeroT;
		return pinaryArray[n - 1];
	}
}

int main()
{
	int n;

		cin >> n;

		Pinary t = PinaryCheck(n);
		cout << t.zeroT + t.oneT;
    return 0;
}