ÁÙ¼¼¿ì±â ´ëȸ Ç®ÀÌ

ÀÌ ¹®Á¦¿¡¼­, ¾î¸°À̵éÀº µÎ ¹ø ÀÌ»ó ¿òÁ÷ÀÏ ÇÊ¿ä°¡ ¾ø´Ù. µû¶ó¼­ Á¤·ÄµÈ ¾ÆÀ̵éÀ» »ý°¢ÇØ º¸¾ÒÀ» ¶§, ¾ÕÀ¸·Î ¿Å°ÜÁø ¾ÆÀ̵é, ¿Å°ÜÁöÁö ¾ÊÀº ¾ÆÀ̵é, µÚ·Î ¿Å°ÜÁø ¾ÆÀ̵é·Î ³ª´­ ¼ö ÀÖ´Ù. ÆíÀÇ»ó ¼ø¼­´ë·Î A, B, C¶ó ÇÏÀÚ.

A´Â ¸ðµÎ °¡Àå ¾ÕÀ¸·Î ¿òÁ÷¿´±â ¶§¹®¿¡, Ç×»ó Bº¸´Ù ¾Õ¿¡ ÀÖ´Ù. ºñ½ÁÇÑ ÀÌÀ¯·Î, C´Â Bº¸´Ù Ç×»ó µÚ¿¡ ÀÖ´Ù. ´Ù½Ã ¸»ÇØ ¾ÆÀ̵éÀº A B C ¼ø¼­·Î ÀÖ°Ô µÈ´Ù. ¿©±â¼­ ¾ÆÀ̵éÀ» ¿Å±ä Ƚ¼ö´Â n(A)+n(C)¿Í °°´Ù.

¶ÇÇÑ B´Â ¿Å°ÜÁöÁö ¾Ê¾Ò±â ¶§¹®¿¡ ÁÖ¾îÁø µ¥ÀÌÅÍ¿¡¼­ ¼ø¼­´ë·Î ³ªÅ¸³ª°Ô µÈ´Ù. ±×¸®°í A B C´Â Á¤·ÄµÇ¾î ÀÖ ´Â »óÅÂÀ̱⠶§¹®¿¡ B´Â ¿¬¼ÓÀûÀ¸·Î ÀÌ·ç¾îÁ®ÀÖ´Ù. ¹®Á¦¿¡¼­ ¿øÇÏ´Â ´äÀ» ã±â À§Çؼ­´Â n(B)¸¦ °¡Àå Å©°Ô ÇØ¾ß Çϱ⠶§¹®¿¡, °¡Àå ±ä ¿¬¼ÓÀûÀ¸·Î Áõ°¡ÇÏ´Â ºÎºÐ ¼ö¿­À» ã´Â ¹®Á¦·Î »ý°¢ÇÒ ¼ö ÀÖ´Ù.

¿¹¸¦ µé¾î, 5 2 3 4 7 1 6 ¿¡¼­´Â 2 3 4°¡ °¡Àå ±ä ¿¬¼ÓÀûÀ¸·Î Áõ°¡ÇÏ´Â ºÎºÐ ¼ö¿­ÀÌ µÇ°í, µû¶ó¼­ ´äÀº 7-3=4°¡ µÈ´Ù.

¸¶Áö¸· ¼ýÀÚ°¡ i ÀÎ ÃÖÀå ¿¬¼Ó Áõ°¡ ¼ö¿­ÀÇ ±æÀ̸¦ m(i)¶ó ÇÏÀÚ. i ÀÇ À§Ä¡°¡ i-1 ÀÇ À§Ä¡º¸´Ù µÚ¿¡ ÀÖÀ¸¸é m(i) = m(i-1) + 1 ÀÌ µÇ°í, ±×·¸Áö ¾ÊÀ¸¸é m(i) = 1 ÀÌ µÈ´Ù. ÀÌ´Â °¢ ¼ýÀÚµéÀÌ ¾îµð¿¡ À§Ä¡ÇÏ´ÂÁö¸¦ ±â·ÏÇØ ³õÀ¸¸é O(N) ¿¡ ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Ù.

   

[ȨÀ¸·Î]  [µÚ ·Î]