백준 1005 ACM Craft

처음에 이 문제의 정답률이 17%인걸 안보고

호옹 잼겠다

싶어서 그냥 푼 문제

근데 그냥 풀었더니

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이게 DP 처음 푼 문제였는데

난 원래 C#을 좋아하는 사람이여서 C#으로 풀었더니

시간초과에 메모리 초과에.. 4번이나 틀려서 C++로 고쳤다

그리고 C++로 고쳐서 for each를 썼더니

비쥬얼스튜디오에선 잘돼던게 컴파일 에러가 뜨더라

이때 이후로 비쥬얼 스튜디오를 거르고 코드블록을 쓴다.

근데 비쥬얼 스튜디오가 편하긴 편한데..... 

그냥 한번 틀리면 돼는데 굳이 불편한 코드블록 써야돼나 싶기도 하고... 고민중

이건 첨 제출한 C#코드

using System;
using System.Collections.Generic;

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            int testcase = Int32.Parse(Console.ReadLine());
            for (int i = 0; i < testcase; i++)
            {
                string[] firstLine = Console.ReadLine().Split(' '); //건물 갯수 , 건물 순서 규칙 갯수
                int buildingNum = Int32.Parse(firstLine[0]);
                int OrderRuleNum = Int32.Parse(firstLine[1]);

                string[] secondLine = Console.ReadLine().Split(' '); // 각 건물당 걸리는 시간
                List<short> constructTime = new List<short>();
                for (int j = 0; j < buildingNum; j++)
                {
                    constructTime.Add(Int16.Parse(secondLine[j]));
                }
                
                
                List<List<short>> connectionArray = new List<List<short>>();// 연결 정보 초기화
                for (int x = 0; x < buildingNum; x++)
                {
                    connectionArray.Add(new List<short>());
                }

                for (int j = 0; j < OrderRuleNum; j++)
                {
                    string[] connectionLine = Console.ReadLine().Split(' ');
                    short aa = Convert.ToInt16(Int32.Parse(connectionLine[1]) - 1);
                    connectionArray[Int32.Parse(connectionLine[0]) - 1].Add(aa);
                }

                int goal = Int32.Parse(Console.ReadLine());

                //입력 및 정보 초기화 끝

                List<short> memoization = new List<short>(); //메모이제이션. 각 노드당 최소 시간 저장
                for(int j = 0; j < buildingNum; j++)
                {
                    memoization.Add(0);
                }
                //전개방법 : 너비 우선 탐색을 진행하면서 메모이제이션에 최대 시간을 갱신.

                memoization[0] = constructTime[0];
                
                Queue<short> graphQ = new Queue<short>();
                graphQ.Enqueue(0);

                while(graphQ.Count > 0)
                {
                    short nowNode = graphQ.Dequeue();
                    short nowNodeConstructTime = memoization[nowNode];
                    for(int j = 0; j < connectionArray[nowNode].Count; j++)
                    {
                        short newNode = connectionArray[nowNode][j];
                        graphQ.Enqueue(newNode);

                        if (nowNodeConstructTime + constructTime[newNode] > memoization[newNode])
                        {
                            memoization[newNode] = Convert.ToInt16(nowNodeConstructTime + constructTime[newNode]);
                        }
                        
                    }
                }
                Console.WriteLine(memoization[goal-1]);
            }
        }
    }
}

어쨋거나 

C++로 고쳤는데도 메모리초과가 뜨더라

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int testcase;
int timeMemo[1000];
int connection[1000][1000];
int connectionSize[1000];
int constructTime[1000];

int main(void) {

	cin >> testcase;

	while (testcase > 0) {
		testcase--;

		int buildingNum;
		int OrderRuleNum;
		cin >> buildingNum >> OrderRuleNum;

		int temptime = 0;
		for (int i = 0; i < buildingNum; i++) {
			cin >> temptime;
			constructTime[i] = temptime;
		}


		for (int i = 0; i < OrderRuleNum; i++) {
			int from, end;
			cin >> from >> end;
			connection[from - 1][connectionSize[from - 1]] = end - 1;
			connectionSize[from - 1]++;
		}

		int goal;
		cin >> goal;



		timeMemo[0] = constructTime[0];

		queue<int> graphQ;
		graphQ.push(0);

		while (!graphQ.empty()) {
			int nowNode = graphQ.front();
			graphQ.pop();
			int nowNodeConstructTime = timeMemo[nowNode];

			for(int i = 0 ; i < connectionSize[nowNode] ; i ++){
				int nextNode = connection[nowNode][i];
				graphQ.push(nextNode);
				if (nowNodeConstructTime + constructTime[nextNode] > timeMemo[nextNode]) {
					timeMemo[nextNode] = nowNodeConstructTime + constructTime[nextNode];
				}
			}
		}

		cout << timeMemo[goal-1] << endl;

		for (int i = 0; i < buildingNum; i++) {
			timeMemo[i] = 0;
			for (int j = 0; j < connectionSize[i]; j++) {
				connection[i][j] = 0;
			}
			connectionSize[i] = 0;
			constructTime[i] = 0;
		}

	}

	return 0;
}

이게 그 코드인데

진짜 지금도 똥멍청이지만 이때는 더 똥멍청이라서 배열크기 문젠줄 모르고 몇번을 고쳤었는지..

나중에 해도해도 안돼서 배열크기를 줄였더니 바로 맞았다

(중간에 한번 틀린건 배열을 잘못 줄여서.....ㅋㅋ)

memo[n]은 'n번째 건물을 짓기 위한 시간' 이고

connection[a][b]는 'a 다음에 b를 짓는 규칙이 있는지' 에 대해 true/false로 나타내고

construcTime[x]는 변수 명에서 알 수 있듯이 'x번째 건물'만' 짓는 시간' 이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int memo[1001];
bool connection[1001][1001];
int constructTime[1001];

void InitAllValue() {
	for (int i = 0; i < 1001; i++) {
		memo[i] = 0;
		constructTime[i] = 0;
		for (int j = 0; j < 1001; j++) {
			connection[i][j] = false;
		}
	}
}

int solve(int goal, int buildingNum) {

	if (memo[goal] > 0) {
		return memo[goal];
	}

	int result = 0;
	for (int i = 0; i < buildingNum; i++) {
		if (connection[i][goal]) {
			result = max(result, solve(i, buildingNum));
		}
	}
	memo[goal] = result + constructTime[goal];
	return memo[goal];	

}

int main() {
	int testcase;

	cin >> testcase;

	while (testcase > 0) {
		testcase--;

		InitAllValue();

		int buildingNum;
		int OrderRuleNum;
		cin >> buildingNum >> OrderRuleNum;

		int temptime = 0;
		for (int i = 0; i < buildingNum; i++) {
			cin >> temptime;
			constructTime[i] = temptime;
		}


		for (int i = 0; i < OrderRuleNum; i++) {
			int from, end;
			cin >> from >> end;
			connection[from - 1][end - 1] = true;
		}

		int goal;
		cin >> goal;



		int result = solve(goal - 1, buildingNum);

		cout << result << endl;

	}


}

이 날 이후로 C++을 쓴다.... C# 편한데...