https://www.acmicpc.net/problem/11066


거의 일주일동안 푼 문제, 답을 봐도 뭔소린지 모르겠어서 멘탈이 터졌다.


문제

소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.


예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.


소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.


입력

프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다. 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다. 파일의 크기는 10,000을 초과하지 않는다.


출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데, 모든 장을 합치는데 필요한 최소비용을 출력한다.


예제 입력 1 

2

4

40 30 30 50

15

1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 1 

300

864


코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
 
#define min(a,b)            (((a) < (b)) ? (a) : (b))
 
long long dp[501][501];
long long sum[501];
int T, K;
 
int main()
{
    std::cin >> T;
    for (int testCase = 0; testCase < T; ++testCase)
    {
        std::cin >> K;
        for (int i = 1; i <= K; ++i)
        {
            std::cin >> sum[i];
            sum[i] += sum[i - 1];
        }
        for (int x = 2; x <= K; ++x)
            for (int y = 1; y + x - 1 <= K; ++y)
            {
                dp[y][x + y - 1] = 2147483647;
                for (int m = y + 1; m - y < x; ++m)
                    dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]);
            }
        std::cout << dp[1][K] << '\n';
 
 
        for (int y = 0; y <= K + 2; ++y)
        {
            for (int x = 0; x <= K + 2; ++x)
            {
                std::cout.width(3);
                std::cout << dp[y][x] << ' ';
            }
            std::cout << '\n';
        }
    }
    return 0;
}
cs


예제 1의 설명으로는 좀 애매한 부분이 있어서.. 예제 2의 동작원리를 보게 되었다.



행렬은 이러한 숫자들로 구성이 되어 있는데,


3중 반복문이 어떻게 동작하는지 살펴봐야 한다.


1
2
3
4
5
6
7
for (int x = 2; x <= K; ++x)
    for (int y = 1; y + x - 1 <= K; ++y)
    {
        dp[y][x + y - 1] = 2147483647;
        for (int m = y + 1; m - y < x; ++m)
            dp[y][x + y - 1] = min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]);
    }
cs



행렬은 x좌표가 2에서 시작한다. y는 x좌표의 값을 더해(-1도 추가) 입력받은 K장까지 증가하게 된다. int y = 1; y + x - 1 <= K; ++y


 y는 1부터 15까지 모든 행을 다 순회하기 때문에 1에서 시작한다. y + x - 1 <= K인 이유는 y <= K일 경우에 행렬 오버플로가 발생하기 때문


m은 양옆의 원소들을 비교하기 위해 존재하는 반복문이다. 자세한 동작은 계속 설명하면서 다시 보자.


첫번째 반복의 상황에선 x = 2, y = 1일 때, m = y + 1이 2, 즉 1 < 2(m - y < x) 이기 때문에 x = 2, y = 1, m = y + 1 일 때



dp[y][x + y - 1]이 2147483647(INT_MAX)이고,


min(dp[y][x + y - 1], dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1])

 =

dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

dp[2][2] + dp[1][1] + sum[2] - sum[0]

0              +    0        +  22(sum[2])   -  0(sum[0])

이기 때문에 22가 들어가게 되는 것이다.


y가 2일 때는 25(sum[x + y - 1] = sum[3]) - 1(sum[y - 1] = sum[1]) 이다.


즉,

dp[3][3] + dp[2][2] + sum[3] - sum[1] = 24이다.


아직까진 반복문 m이 한번밖에 돌지 않는다. 또한 동작도 납득할 수 있는 수준이다.



이제 x = 3 일 때, y가 어떻게 동작하는지 알아야 한다.


for (int m = y + 1; m - y < x; ++m)이다. 즉 m = 2일때, m - y < x(2 - 1 < 2), 반복문은 두번 반복된다.


m = 2 일 때,

y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[2][3] + dp[1][2](0 + 24) 이다.


dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

즉, 24 + 25 = 49 이다. dp[y][x + y - 1]는 49이다.


m = 3 일 때,

y = 1이고, 식에 의해 25(sum[3]) - 0(sum[0]) = 25이다. dp[m][x + y - 1] + dp[y][m - 1]는 dp[3][3] + dp[1][1](22 + 0) 이다.


dp[m][x + y - 1] + dp[y][m - 1] + sum[x + y - 1] - sum[y - 1]

즉, 22 + 25 = 47 이다. 49 > 47 이기 때문에 dp[y][x + y - 1]는 47이다.



혼란스러운 머리를 부여잡고 여기까지 따라왔다면 이것 또한 이해할수있따


dp[1][4]는 (22 + 7) + (1 + 21 + 3 + 4) = 58 이고, 

dp[2][5]는 (19 + 0) + (21 + 3 + 4 + 5) = 52 이다.


사진상의 행렬 비교 순서는 m = 2 일 때,

(35 + 0) + (1 + 21 + 3 + 4)

(7 + 22) + (1 + 21 + 3 + 4)

(0 + 47) + (1 + 21 + 3 + 4)


이 중 가장 작은것은 58이기 때문에, dp[1][4]는 58이 들어가는 것



같은 원리다. 계산은 이와 같은 로직으로 돌아가게 된다.


어째서 이러한 동작을 하게 되냐면,


잘 모르겠다ㅎ 대충 이분해서 최솟값을 계산하는 것은 얼추 알 것 같다. 설명할 자신은 없지만



첫 번째 사진은 1, 21 ~ 32 중 최소 비용을 쓴 크기 (839 + 0) + sum[15]

두 번째 사진은 1 ~ 21, 3 ~ 32 중 최소 비용을 쓴 크기 (739 + 22) + sum[15]

...

n  번째 사진은 1 ~ 35, 5 ~ 32 중 최소 비용을 쓴 크기 (515 + 144) + sum[15]

515 : 1 ~ 35 중 최소 비용

144 : 5 ~ 32 중 최소 비용

... K번까지 돌아가는 것이다.


그냥 그러려니 하고 암기하자...

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

2. C++언어 역사 개요..?  (0) 2019.10.07
1. 희망의 나라로 알고리즘  (0) 2019.10.07
백준 1912: 연속합(DP)  (0) 2019.08.27
백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23

ESP - Stack pointer register


ESP 레지스터 : 스택의 크기를 조정할 때 사용되는 레지스터. 스택의 최상단 주소값을 가진다.

 -> 스택의 크기를 나타냄


Intel CPU에서는 스택이 거꾸로 자란다.


ESP는 다음 번 DATA를 PUSH할 위치가 아닌, 다음에 POP 했을 때 뽑아낼 데이터의 위치를 가리킨다.

 -> std::stack::top()의 주소라고 생각하면 될듯.


어셈블리에서 esp에 PUSH를 하면 esp 값이 n감소한다.


 n? : msvc 2017 기준, 0C0h(192) 감소한다. 밑의 디스어셈블리 참고


감소하는 이유는 다음과 같다. 높은주소 → 낮은주소


EBP - Base pointer register


EBP 레지스터 : 스택프레임 형태로 저장된 함수의 지역변수, 전달 인자를 참조 & 값의 수정 시 사용되는 레지스터.


현재 스택의 가장 바닥을 가리키는 포인터.


새로운 함수 B가 호출되면, EBP 레지스터 값은 지금까지 사용했던 스택 A의 위를 가리킨다. 그리고 새로운 스택(함수 공간)이 시작


따라서 EBP는 새로운 함수가 호출되거나, 현재 실행중인 함수가 종료되면 값이 달라진다.


새로운 함수를 호출할 때, EBP 레지스터 값

전달 인자를 ESP 레지스터로 참조할 수는 있지만 어셈블리 코드 유지가 힘들다.


EBP는 고정적이지만 ESP는 명령을 수행 시 값이 변하기 때문에 매번 수정해주어야 하기 때문.




00E85720 push ebp : 이전 스택의 베이스 주소(따로 첨부는 안했지만 main함수였음)를 저장


00E85721 mov ebp, esp  : 현재 스택의 꼭대기(esp)를 새로운 스택의 base(ebp)로 복사

(새로운 스택의 시작)


그 밑에도 뭐가 주루룩 있지만 일단 여기까지만



기본적인 레지스터 종류


일반 레지스터

EAX, EBX, ECX, EDX


일반주소 레지스터

ESP, EBP, ESI, EDI


그 외 레지스터

EIP



EAX (Extended Accumulator Register)

 - 산술, 논리연산


산술, 논리연산의 중심이 되는 레지스터

주로 이 레지스터를 사용해 산술, 논리 연산을 수행


함수의 리턴 값을 저장하는 레지스터다.

(그렇기 때문에 리턴값이 2개 이상이 될 수 없다.)


EBX (Extended? Base Register)

 - 간접 주소 지정


간접 주소 지정 시 사용된다.

ebx 1000

jmp 1000 //직접 지정

jmp ebx // 간접 지정


int a[5] 에서 배열의 메모리 접근 시 a[2]를 사용되는 0 ~ 4, 이러한 인덱스 넘버가 바로 간접 번지이다.

 - a의 3번째 주소에 접근해라!


ECX (Extended? Count Register)

 - 반복 카운터


루프와 같은 명령의 반복 수행이 필요할 때 반복 횟수 지정에 주로 사용, (while, for과 다르다. 어셈블리를 위한 반복이다)


ex) ECX에 5를 넣었을 때, ECX 값이 0이 될 때까지 반복한다. ECX 값은 감소한다.


EDX (Extended? Data Register)

 - EAX를 도와주는 역할


아 귀찮다. 나중에 더 필요하면 공부함

저작자표시 (새창열림)

'프로그래밍' 카테고리의 다른 글

클린 코드(미완)  (0) 2023.03.01
COM  (0) 2020.11.06
XML, XML DOM  (0) 2020.11.06
FSM  (0) 2019.07.24
더블과 플로트, FPU에 관해 (6 / 2)  (0) 2019.06.09

https://www.acmicpc.net/problem/1912



 

 시간 제한

 2 초 

 메모리 제한

 128 MB

 제출

 51339

 정답

 14220

 맞은 사람

 9806

 정답 비율 

 27.120%


문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.


예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.


입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.


기존 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
 
int dp[100010];
int arr[100010];
 
int max(int first, int second) 
{ 
    return first > second ? first : second;
}
 
int main()
{
    int n = 0;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
        dp[i] = -1001;
    }
    dp[0] = arr[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
    }
    std::sort(dp, dp + n);
    std::cout << dp[n - 1];
    return 0;
}
cs

시간 20ms


바꾼 코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
 
int dp[100010];
int arr[100010];
 
int max(int first, int second) { return first > second ? first : second; }
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    int n = 0;
    std::cin >> n;
    dp[0] = -1001;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> arr[i];
        dp[i] = -1001;
        dp[i] = max(arr[i], arr[i] + dp[i - 1]);
    }
    std::sort(dp, dp + n + 1);
    std::cout << dp[n];
    return 0;
}
cs

시간 8ms


어이어이 너무 쉬운거 아니냐고 wwwwwww


LIS LCS에서 뚝배기터지고 나온 문제라 와 시발 얼마나 어려울까 해쓴ㄴ데


문제가 생각보다 너무 쉬울것같아서 아.. 뭔가 어려운게 있겠지? 있겠지? 해서

(코드 짠시간보다 이게 될까 안될까 고민하는 시간이 더 길었다)


부들부들 떨면서 제출했는데 그냥 통과대버렷다


쉬운문제는 맞는것같은데 왤캐 정답률이 낮지


히히ㅣㅎ킿킿ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

1. 희망의 나라로 알고리즘  (0) 2019.10.07
백준 11066: 파일 합치기(DP)  (0) 2019.09.06
백준 9251: LCS(DP)  (0) 2019.08.26
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23

https://www.acmicpc.net/board/view/28163


5시간동안 개삽질하고


답 5분 보고 어이없어서


멘탈터짐


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
unsigned int max(unsigned int first, unsigned int second)
{
    return first > second ? first : second;
}
 
unsigned int dp[1001][1001];
 
int main()
{
    std::string A, B;
    std::cin >> A >> B;
    for (int y = 1; y <= A.size(); ++y)
    {
        for (int x = 1; x <= B.size(); ++x)
        {
            if (A[y - 1] == B[x - 1])
                dp[y][x] += dp[y - 1][x - 1] + 1;
            else
                dp[y][x] = max(dp[y][x - 1], dp[y - 1][x]);
        }
    }
    for (int y = 0; y <= A.size(); ++y)
    {
        for (int x = 0; x <= B.size(); ++x)
        {
            std::cout << dp[y][x]; //dp[A.size()][B.size()]가 정답
        }
        std::cout << '\n';
    }
    return 0;
}
 
cs


2차원배열을 이용하는 것도 참


생각도 못했다


걍 너무 내가 병신쪼다같고 막.. 그래....


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
unsigned int getlen(int it, unsigned int n)
{
    //KJFSDFLKDF
    int tmp = 1;
    int pos = n;
    for (unsigned int i = it; i < str1.size(); ++i)
    {
        //findPos = prePos;
        //KJSDFKSDFLKDFJS SKDJKFLSKDJFLKSDJF
        auto finder = str2.find(str1[i], pos);
        if (finder == std::string::npos) continue;
        if (dp2[finder] != 0 && dp2[finder] <= tmp) { ++pos; --i;  continue; }
        unsigned int j = finder;
        while (j < str2.size())
        {
            if (dp2[j] != 0) break;
            ++j;
            //if (tmp > dp2[j] && str2[j] == str1[i]) break;
        }
        if (tmp > dp2[j] && dp2[finder] != 0) { ++pos; --i;  continue; }
        if (j == str2.size())
        {
            dp2[finder] = ++tmp;
        }
        else
        {
            if (str1[i] == str2[j] && tmp < dp2[j]) continue;
            dp2[finder] = dp2[j];
            tmp = dp2[j];
            dp2[j] = 0;
        }
        //prePos = finder;
        //int jtmp = 0;
        //for (unsigned int j = i + 1; j < str1.size(); ++j)
        //{
        //    findPos = finder;
        //    finder = str2.find(str1[j], findPos);
        //    if(finder == std::string::npos) continue;
        //    ++jtmp;
        //    if (finder == str2.size() - 1) break;
        //}
        //cnt = cnt > tmp + jtmp ? cnt : tmp + jtmp;
    }
    std::cout << '\n';
    cnt = cnt > tmp ? cnt : tmp;
    for (int i = 0; i < str2.size(); ++i)
        std::cout << dp2[i] << ' ';
    return cnt;
}
 
int main()
{
    std::cin >> str1 >> str2;
    int dcnt = 0;
    for (unsigned int i = 0; i < str1.size(); ++i)
    {
        cnt = 0;
        auto startPoint = str2.find(str1[i]);
        if(startPoint == std::string::npos) continue;
        std::cout << str2[startPoint] << ' ';
        dp1[dcnt++] = getlen(i + 1, startPoint + 1);
    }
    std::sort(dp1, dp1 + str1.size());
    std::cout << dp1[str1.size() - 1];
    return 0;
}
cs


똥꼬쑈의 흔적


결국 대패배


저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 11066: 파일 합치기(DP)  (0) 2019.09.06
백준 1912: 연속합(DP)  (0) 2019.08.27
백준 2565: 전깃줄(DP)  (0) 2019.08.23
백준 11054: 가장 긴 바이토닉 부분 수열(DP)  (0) 2019.08.23
백준 11053: 가장 긴 증가하는 부분 수열(DP)  (0) 2019.08.22

+ Recent posts

티스토리툴바