ÀÌ ¹®Á¦¿¡¼, ¾î¸°À̵éÀº µÎ ¹ø ÀÌ»ó ¿òÁ÷ÀÏ ÇÊ¿ä°¡ ¾ø´Ù. µû¶ó¼ Á¤·ÄµÈ ¾ÆÀ̵éÀ» »ý°¢ÇØ º¸¾ÒÀ» ¶§, ¾ÕÀ¸·Î ¿Å°ÜÁø ¾ÆÀ̵é, ¿Å°ÜÁöÁö ¾ÊÀº ¾ÆÀ̵é, µÚ·Î ¿Å°ÜÁø ¾ÆÀ̵é·Î ³ª´ ¼ö ÀÖ´Ù. ÆíÀÇ»ó ¼ø¼´ë·Î 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) ¿¡ ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Ù.