28709번 - 와일드카드 괄호 문자열 다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB119227323626.020%

문제

‘(’, ‘)’로 이루어진 문자열이 올바른 괄호 문자열이라는 것은 다음을 의미합니다.

  • $S$가 빈 문자열이면, $S$는 올바른 괄호 문자열입니다.
  • $S$가 올바른 괄호 문자열이면, $S$의 앞뒤에 각각 ‘(’와 ‘)’를 붙여 만든 문자열 “($S$)” 는 올바른 괄호 문자열입니다.
  • $S$와 $T$가 올바른 괄호 문자열이면, $S$와 $T$를 붙여 만든 문자열 “$ST$”는 올바른 괄호 문자열입니다.
  • 위 세 규칙을 통해 만들 수 없는 문자열은 올바른 괄호 문자열이 아닙니다.

예를 들어, “(())()”, “()()”은 올바른 괄호 문자열이고 “)(”, “())(”는 올바른 괄호문자열이 아닙니다.

문자열 $S$가 주어집니다. $S$는 ‘(’, ‘)’, ‘?’, ‘*’로 이루어진 문자열입니다. ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’와 ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$를 올바른 괄호 문자열로 만들 수 있나요?

입력

첫 줄에 테스트케이스의 수 $T$가 주어집니다. $(1 \le T \le 10\,000)$

각 테스트케이스의 첫 줄에는 ‘(’, ‘)’, ‘?’, ‘*’로 이루어진 길이가 $1$ 이상 $500\,000$ 이하인 문자열 $S$가 주어집니다.

입력에서 주어진 문자열 $S$의 길이 합은 $500\,000$을 넘지 않습니다.

출력

각 테스트케이스마다 한 줄에 하나씩, ‘?’ 문자를 ‘(’이나 ‘)’로, ‘*’ 문자를 ‘(’, ‘)’로 이루어진 길이가 $0$ 이상인 원하는 문자열로 대체하여 $S$를 올바른 괄호 문자열로 만들 수 있다면 “YES”, 불가능하면 “NO”를 출력하세요.

예제 입력 1 

4
()??))
())*(())
*)))(((*
?()(?*))(()?

예제 출력 1 

YES
NO
YES
YES
  • 첫째 테스트 케이스는 두 개의 ‘?’를 ‘(’로 대체해서 $S$를 올바른 괄호 문자열 “()(())”로 만들 수 있습니다.
  • 두 번째 테스트 케이스는 ‘*’을 어떻게 대체해도 $S$를 올바른 괄호 문자열로 만들 수 없습니다.
  • 세 번째 테스트 케이스는 두 개의 ‘*’을 각각 “(((” 와 “)))”로 대체해서 $S$를 올바른 괄호 문자열 “((()))((()))”로 만들 수 있습니다.
  • 네 번째 테스트 케이스는 ‘?’, ‘?’, ‘*’, ‘?’를 차례로 ‘(’, ‘)’, “(”, ‘)’로 대체해서 $S$를 올바른 괄호 문자열 “(()()())(())”로 만들 수 있습니다.
W3sicHJvYmxlbV9pZCI6IjI4NzA5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNjQwXHVjNzdjXHViNGRjXHVjZTc0XHViNGRjIFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPiZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPik8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWIyZTRcdWM3NGNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRTJFx1YWMwMCBcdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViYTc0LCAkUyRcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3ODVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiRTJFx1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YmE3NCwgJFMkXHVjNzU4IFx1YzU1ZVx1YjRhNFx1YzVkMCBcdWFjMDFcdWFjMDEgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oPFwvY29kZT48XC9zcGFuPiZyc3F1bztcdWM2NDAgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bztcdWI5N2MgXHViZDk5XHVjNWVjIFx1YjljY1x1YjRlMCBcdWJiMzhcdWM3OTBcdWM1ZjQgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oPFwvY29kZT48XC9zcGFuPiRTJDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyZHF1bzsgXHViMjk0IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzg1XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT4kUyRcdWM2NDAgJFQkXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViYTc0LCAkUyRcdWM2NDAgJFQkXHViOTdjIFx1YmQ5OVx1YzVlYyBcdWI5Y2NcdWI0ZTAgXHViYjM4XHVjNzkwXHVjNWY0ICZsZHF1bzskU1QkJnJkcXVvO1x1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc4NVx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzA0IFx1YzEzOCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyZDlcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oKCkpKCk8XC9jb2RlPjxcL3NwYW4+JnJkcXVvOywgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oKSgpPFwvY29kZT48XC9zcGFuPiZyZHF1bztcdWM3NDAgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzRcdWFjZTAgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pKDxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87LCAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPigpKSg8XC9jb2RlPjxcL3NwYW4+JnJkcXVvO1x1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4XHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzU0NFx1YjJkOVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYjM4XHVjNzkwXHVjNWY0ICRTJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICRTJFx1YjI5NCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bzssICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPio8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzg1XHViMmM4XHViMmU0LiAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPj88XC9jb2RlPjxcL3NwYW4+JnJzcXVvOyBcdWJiMzhcdWM3OTBcdWI5N2MgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oPFwvY29kZT48XC9zcGFuPiZyc3F1bztcdWM3NzRcdWIwOTggJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bztcdWI4NWMsICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KjxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IFx1YmIzOFx1Yzc5MFx1Yjk3YyAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1YzY0MCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPik8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0XHVhYzAwICQwJCBcdWM3NzRcdWMwYzFcdWM3NzggXHVjNmQwXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWIzMDBcdWNjYjRcdWQ1NThcdWM1ZWMgJFMkXHViOTdjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMDk4XHVjNjk0PzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4ICRUJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuICQoMSBcXGxlIFQgXFxsZSAxMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bzssICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPio8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0XHVhYzAwICQxJCBcdWM3NzRcdWMwYzEgJDUwMFxcLDAwMCQgXHVjNzc0XHVkNTU4XHVjNzc4IFx1YmIzOFx1Yzc5MFx1YzVmNCAkUyRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmIzOFx1Yzc5MFx1YzVmNCAkUyRcdWM3NTggXHVhZTM4XHVjNzc0IFx1ZDU2OVx1Yzc0MCAkNTAwXFwsMDAwJFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVjMmI1XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjksICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IFx1YmIzOFx1Yzc5MFx1Yjk3YyAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yzc3NFx1YjA5OCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPik8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yjg1YywgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiZyc3F1bzsgXHViYjM4XHVjNzkwXHViOTdjICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPik8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0XHVhYzAwICQwJCBcdWM3NzRcdWMwYzFcdWM3NzggXHVjNmQwXHVkNTU4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yjg1YyBcdWIzMDBcdWNjYjRcdWQ1NThcdWM1ZWMgJFMkXHViOTdjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0ICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+WUVTPFwvY29kZT48XC9zcGFuPiZyZHF1bzssIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YmE3NCAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPk5PPFwvY29kZT48XC9zcGFuPiZyZHF1bztcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInNhbXBsZV9leHBsYWluXzEiOiI8dWw+XHJcblx0PGxpPlx1Y2NhYlx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4/PFwvY29kZT48XC9zcGFuPiZyc3F1bztcdWI5N2MgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oPFwvY29kZT48XC9zcGFuPiZyc3F1bztcdWI4NWMgXHViMzAwXHVjY2I0XHVkNTc0XHVjMTFjICRTJFx1Yjk3YyBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNCAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPigpKCgpKTxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiZyc3F1bztcdWM3NDQgXHVjNWI0XHViNWJiXHVhYzhjIFx1YjMwMFx1Y2NiNFx1ZDU3NFx1YjNjNCAkUyRcdWI5N2MgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWMyYjVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWI0NTAgXHVhYzFjXHVjNzU4ICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KjxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87XHVjNzQ0IFx1YWMwMVx1YWMwMSAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPigoKDxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87IFx1YzY0MCAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPikpKTxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87XHViODVjIFx1YjMwMFx1Y2NiNFx1ZDU3NFx1YzExYyAkUyRcdWI5N2MgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjQgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oKCgpKSkoKCgpKSk8XC9jb2RlPjxcL3NwYW4+JnJkcXVvO1x1Yjg1YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMTI0IFx1YmM4OFx1YzlmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0ICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPj88XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiZyc3F1bzssICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87XHViOTdjIFx1Y2MyOFx1Yjg0MFx1Yjg1YyAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bzssICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPik8XC9jb2RlPjxcL3NwYW4+JnJzcXVvO1x1Yjg1YyBcdWIzMDBcdWNjYjRcdWQ1NzRcdWMxMWMgJFMkXHViOTdjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0ICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KCgpKCkoKSkoKCkpPFwvY29kZT48XC9zcGFuPiZyZHF1bztcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIyODcwOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldpbGRjYXJkIFBhcmVudGhlc2VzIFN0cmluZyIsImRlc2NyaXB0aW9uIjoiPHA+QSBzdHJpbmcgY29uc2lzdHMgb2YgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oPFwvY29kZT48XC9zcGFuPiZyc3F1bzsgYW5kICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KTxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IGlzIGEgPGVtPnZhbGlkIHBhcmVudGhlc2VzIHN0cmluZyA8XC9lbT5pZiBpdCBtZWV0cyB0aGUgZm9sbG93aW5nIGNyaXRlcmlhOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPklmICRTJCBpcyBhbiBlbXB0eSBzdHJpbmcsICRTJCBpcyBhIHZhbGlkIHBhcmVudGhlc2VzIHN0cmluZy48XC9saT5cclxuXHQ8bGk+SWYgJFMkIGlzIGEgdmFsaWQgcGFyZW50aGVzZXMgc3RyaW5nLCB0aGUgc3RyaW5nICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4kUyQ8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KTxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87IGNyZWF0ZWQgYnkgYXR0YWNoaW5nICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IGFuZCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPik8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOyByZXNwZWN0aXZlbHkgdG8gdGhlIGZyb250IGFuZCBiYWNrIG9mICRTJCBpcyBhIHZhbGlkIHBhcmVudGhlc2VzIHN0cmluZy48XC9saT5cclxuXHQ8bGk+SWYgJFMkIGFuZCAkVCQgYXJlIHZhbGlkIHBhcmVudGhlc2VzIHN0cmluZ3MsIHRoZSBzdHJpbmcgJmxkcXVvOyRTVCQmcmRxdW87IGNyZWF0ZWQgYnkgY29uY2F0ZW5hdGluZyAkUyQgYW5kICRUJCBpcyBhIHZhbGlkIHBhcmVudGhlc2VzIHN0cmluZy48XC9saT5cclxuXHQ8bGk+QSBzdHJpbmcgdGhhdCBjYW5ub3QgYmUgbWFkZSBieSB0aGUgYWJvdmUgdGhyZWUgcnVsZXMgaXMgbm90IGEgdmFsaWQgcGFyZW50aGVzZXMgc3RyaW5nLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPigoKSkoKTxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87IGFuZCAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPigpKCk8XC9jb2RlPjxcL3NwYW4+JnJkcXVvOyBhcmUgdmFsaWQgcGFyZW50aGVzZXMgc3RyaW5ncyB3aGlsZSAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPikoPFwvY29kZT48XC9zcGFuPiZyZHF1bzsgYW5kICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KCkpKDxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87IGFyZSBub3QgdmFsaWQgcGFyZW50aGVzZXMgc3RyaW5ncy48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBhIHN0cmluZyAkUyQgY29uc2lzdGluZyBvZiAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bzssICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCBhbmQgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiZyc3F1bzsuIENhbiB5b3UgcmVwbGFjZSB0aGUgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4/PFwvY29kZT48XC9zcGFuPiZyc3F1bzsgY2hhcmFjdGVycyB3aXRoICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IG9yICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KTxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCBhbmQgdGhlICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KjxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IGNoYXJhY3RlcnMgd2l0aCBhIHN0cmluZyBvZiB5b3VyIGNob2ljZSBvZiBsZW5ndGggJDAkIG9yIG1vcmUgY29uc2lzdGluZyBvZiAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOyBhbmQgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bzsgdG8gbWFrZSAkUyQgYSB2YWxpZCBwYXJlbnRoZXNlcyBzdHJpbmc/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMsICRUJC4gJCgxIFxcbGUgVCBcXGxlIDEwXFwsMDAwKSQ8XC9wPlxyXG5cclxuPHA+SW4gZWFjaCB0ZXN0IGNhc2UsIHRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGEgc3RyaW5nICRTJCBvZiBsZW5ndGggJDEkIHRvICQ1MDBcXCwwMDAkIGNvbnNpc3Rpbmcgb2YgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oPFwvY29kZT48XC9zcGFuPiZyc3F1bzssICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KTxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPj88XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgYW5kICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KjxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LjxcL3A+XHJcblxyXG48cD5UaGUgc3VtIG9mIHRoZSBsZW5ndGhzIG9mIHRoZSBzdHJpbmcgJFMkIGdpdmVuIGluIHRoZSBpbnB1dCBkb2VzIG5vdCBleGNlZWQgJDUwMFxcLDAwMCQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCAmbGRxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPllFUzxcL2NvZGU+PFwvc3Bhbj4mcmRxdW87IGlmIHlvdSBjYW4gcmVwbGFjZSB0aGUgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4/PFwvY29kZT48XC9zcGFuPiZyc3F1bzsgY2hhcmFjdGVycyB3aXRoICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IG9yICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KTxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCBhbmQgdGhlICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KjxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IGNoYXJhY3RlcnMgd2l0aCBhIHN0cmluZyBvZiB5b3VyIGNob2ljZSBvZiBsZW5ndGggJDAkIG9yIG1vcmUgY29uc2lzdGluZyBvZiAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPig8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOyBhbmQgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pPFwvY29kZT48XC9zcGFuPiZyc3F1bzsgdG8gbWFrZSAkUyQgYSB2YWxpZCBwYXJlbnRoZXNlcyBzdHJpbmcsICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Tk88XC9jb2RlPjxcL3NwYW4+JnJkcXVvOyBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsInNhbXBsZV9leHBsYWluXzEiOiI8dWw+XHJcblx0PGxpPkZvciB0aGUgZmlyc3QgdGVzdCBjYXNlLCB5b3UgY2FuIHJlcGxhY2UgdHdvICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87cyB3aXRoICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IHRvIG1ha2UgJFMkIGEgdmFsaWQgcGFyZW50aGVzZXMgc3RyaW5nICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KCkoKCkpPFwvY29kZT48XC9zcGFuPiZyZHF1bzsuPFwvbGk+XHJcblx0PGxpPkZvciB0aGUgc2Vjb25kIHRlc3QgY2FzZSwgbm8gbWF0dGVyIGhvdyB5b3UgcmVwbGFjZSAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPio8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgeW91IGNhbiYjMzk7dCBtYWtlICRTJCBhIHZhbGlkIHBhcmVudGhlc2VzIHN0cmluZy48XC9saT5cclxuXHQ8bGk+Rm9yIHRoZSB0aGlyZCB0ZXN0IGNhc2UsIHlvdSBjYW4gcmVwbGFjZSB0d28gJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiZyc3F1bztzIHdpdGggJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oKCg8XC9jb2RlPjxcL3NwYW4+JnJkcXVvOyBhbmQgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4pKSk8XC9jb2RlPjxcL3NwYW4+JnJkcXVvOyByZXNwZWN0aXZlbHkgdG8gbWFrZSAkUyQgYSB2YWxpZCBwYXJlbnRoZXNlcyBzdHJpbmcgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oKCgpKSkoKCgpKSk8XC9jb2RlPjxcL3NwYW4+JnJkcXVvOy48XC9saT5cclxuXHQ8bGk+Rm9yIHRoZSBmb3VydGggdGVzdCBjYXNlLCB5b3UgY2FuIHJlcGxhY2UgdGhlICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+PzxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPj88XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgJmxzcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4qPFwvY29kZT48XC9zcGFuPiZyc3F1bzssIGFuZCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPj88XC9jb2RlPjxcL3NwYW4+JnJzcXVvOyBpbiBvcmRlciB3aXRoICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KDxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87LCAmbHNxdW87PHNwYW4gc3R5bGU9XCJjb2xvcjojZTc0YzNjO1wiPjxjb2RlPik8XC9jb2RlPjxcL3NwYW4+JnJzcXVvOywgJmxkcXVvOzxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT4oPFwvY29kZT48XC9zcGFuPiZyZHF1bzssICZsc3F1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KTxcL2NvZGU+PFwvc3Bhbj4mcnNxdW87IHRvIG1ha2UgJFMkIGEgdmFsaWQgcGFyZW50aGVzZXMgc3RyaW5nICZsZHF1bzs8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+KCgpKCkoKSkoKCkpPFwvY29kZT48XC9zcGFuPiZyZHF1bzsuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

출처

Contest > solved.ac > solved.ac Grand Arena #2 I번

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)