[C] 백준 - 2565번: 전깃줄

8월 28일(월) - 다이나믹 프로그래밍 (2565번)

2565번: 전깃줄

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 이전에 풀이했던 11054번 문제에서도 활용했던 LIS 알고리즘을 활용해야할 것으로 예상

 

- 수열 A와 수열 B가 연결되어서 작동(?)해야하므로 구조체로 입력을 A_location, B_location으로 받는다

- 수열 A와 연결되어있는 수열 B가 증가하는 수열을 이루면되므로, qsort는 A_location 값을 오름차순으로 정렬

  이후 B_location[ ] 값으로 비교하며 LIS 알고리즘을 활용하고

  변수 possible을 이용해서 정상적으로 연결된 전깃줄의 개수를 누적으로 저장한다

- 출력은 (전체 전깃줄의 개수 - 정상적으로 연결된 전깃줄의 개수), 즉 (N - possible)을 출력한다

[C] 백준 - 11054번: 가장 긴 바이토닉 부분 수열

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int A_location;
	int B_location;
}pair;

int dp[501];

int compare(const void* a, const void* b)
{
	pair num1 = *(pair*)a;
	pair num2 = *(pair*)b;

	if (num1.A_location > num2.A_location)
	{
		return 1;
	}
	else if (num1.A_location < num2.A_location)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int MAX(int x, int y)
{
	return ((x > y) ? (x) : (y));
}

int main(void)
{
	int N;
	scanf("%d", &N);

	pair* wire = (pair*)malloc(sizeof(pair) * N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d %d", &wire[i].A_location, &wire[i].B_location);
	}

	qsort(wire, N, sizeof(wire), compare);

	for (int i = 0; i <= N; i++)
	{
		dp[i] = 1;

		for (int j = 0; j < i; j++)
		{
			if (wire[i].B_location > wire[j].B_location)
			{
				dp[i] = MAX(dp[i], dp[j] + 1);
			}
		}
	}

	int possible = 0;
	for (int i = 1; i <= N; i++)
	{
		possible = MAX(possible, dp[i]);
	}

	printf("%d", N - possible);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ