원형파이는 학교에서 두 점이 있을 때 자로 두 점을 잇는 것에 대해 배웠습니다.
원형파이는 집에서 배운 내용을 복습해보기로 결심했습니다.
양쪽에 N개씩 점을 그립니다. 각각 위에서부터 1부터 N까지 수를 붙입니다.
(글씨가 삐뚤빼뚤한 점 죄송합니다)
그리고나서 친한 친구 버블몬에게 여러 점의 쌍을 불러달라고 말했습니다.
예를 들어, 버블몬이 1, 2를 부르면 원형파이는 왼쪽 점들 중 1번 점과 오른쪽에서 2번점을 찾아 서로 잇습니다.
원형파이는 버블몬이 부르는대로 전부 선을 그었습니다.
그런데 문제는 몇몇 선들이 서로 교차한다는 것이었습니다. 원형파이의 사전에 '선이 교차한다'란 없습니다.
따라서 몇 개의 선을 지워서 어떤 선도 교차하지 않게 만들어야 합니다.
이 때 한 점에서 여러 선이 그어지면 안됩니다.
버블몬이 부르는 쌍의 개수 K와 버블몬이 부르는 쌍 X, Y가 K개 주어집니다.
그 때, 원형파이가 지워야 하는 최소의 선의 개수를 점화식을 이용하여 구합니다.
(풀이과정 필수, 힌트 요청 가능)
(1)
8 1 8 3 9 2 2 4 1 6 4 10 10 9 7 7 6
(2)
5 72 297 400 223 273 13 195 227 198 400
(3)
20
2423 41
5108 2925
5028 2124
2618 1251
3072 3099
1405 2296
783 2827
491 3143
1246 2995
88 1418
3908 1710
153 493
1686 292
2672 376
3851 2673
334 2038
842 1135
3868 1869
4907 1804
4546 3399
(4)
100
2423 41
5108 2925
5028 2124
2618 1251
3072 3099
1405 2296
783 2827
491 3143
1246 2995
88 1418
3908 1710
153 493
1686 292
2672 376
3851 2673
334 2038
842 1135
3868 1869
4907 1804
4546 3399
2419 1431
3593 641
4664 628
2363 1505
1520 981
904 1684
669 1981
2163 2992
4393 1905
778 257
3035 2089
1842 1736
3366 288
3594 2222
1256 2219
2413 174
3381 2254
4654 507
4361 1370
3548 530
1927 2584
3910 221
1144 1711
2028 1557
4916 295
351 3308
627 763
146 2128
2082 2482
497 2475
4375 1424
2918 1230
4582 2250
2306 341
994 992
2005 1612
3028 3061
481 2861
4877 2914
468 1688
2594 123
2592 2343
3375 1901
4878 3201
1356 622
1150 78
332 3305
3430 330
3451 426
641 962
1591 1821
5035 481
3561 1309
4410 1528
2544 358
3554 3013
2334 234
2428 2777
503 900
1655 1717
1011 365
4493 352
1135 1094
4041 323
2958 193
4096 64
324 2556
2629 1187
1807 76
3092 2623
4734 1463
1999 53
1198 2555
3788 82
467 1082
4197 319
1091 785
2421 762
1269 674
4166 2359
좋아요
0
글쎄요
0
어려워요
0
