시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB181755741.007%

문제

바이너리 스도쿠 게임은 스도쿠의 변형 게임이다. 스도쿠와 비슷하게, 9*9칸으로 이루어져 있고, 이 칸은 각각 3*3 크기의 작은 칸으로 나누어져 있다. 스도쿠와 다른 점은 바이너리 스도쿠에서는 오직 0과 1만 이용해서 스도쿠 퍼즐을 푼다는 점이다.

000 000 000
001 000 100
000 000 000

000 110 000
000 111 000
000 000 000

000 000 000
000 000 000
000 000 000

바이너리 스도쿠의 목표는 최대한 적은 비트를 토글시켜서 각각의 행과 열, 그리고 3*3크기의 구간에 포함된 1의 개수가 짝수개가 되게 하는 것이다.

위의 예제는 3번 만에 퍼즐을 풀 수 있다.

000 000 000
001 000 100
001 000 100

000 110 000
000 110 000
000 000 000

000 000 000
000 000 000
000 000 000

바이너리 스도쿠 퍼즐의 초기 상태가 주어졌을 때, 이 퍼즐을 풀기 위해 필요한 최소 토글의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄부터 아홉 번째 줄 까지 바이너리 스도쿠의 초기 상태가 주어진다.

출력

바이너리 스도쿠를 풀기 위해 필요한 최소 토글의 수를 출력한다.

예제 입력 1

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

예제 출력 1

3

힌트

토글이란 0->1, 1->0으로 바꾸는 연산이다.

W3sicHJvYmxlbV9pZCI6IjU5MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NTggXHViY2MwXHVkNjE1IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YjJlNC4gXHVjMmE0XHViM2M0XHVjZmUwXHVjNjQwIFx1YmU0NFx1YzJiN1x1ZDU1OFx1YWM4YywgOSo5XHVjZTc4XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NCBcdWNlNzhcdWM3NDAgXHVhYzAxXHVhYzAxIDMqMyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjNzkxXHVjNzQwIFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMyYTRcdWIzYzRcdWNmZTBcdWM2NDAgXHViMmU0XHViOTc4IFx1YzgxMFx1Yzc0MCBcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwXHVjNWQwXHVjMTFjXHViMjk0IFx1YzYyNFx1YzljMSAwXHVhY2ZjIDFcdWI5Y2MgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzJhNFx1YjNjNFx1Y2ZlMCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDdjXHViMmU0XHViMjk0IFx1YzgxMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuMDAwIDAwMCAwMDBcclxuMDAxIDAwMCAxMDBcclxuMDAwIDAwMCAwMDBcclxuXHJcbjAwMCAxMTAgMDAwXHJcbjAwMCAxMTEgMDAwXHJcbjAwMCAwMDAgMDAwXHJcblxyXG4wMDAgMDAwIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG4wMDAgMDAwIDAwMDxcL3ByZT5cclxuXHJcbjxwPlx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWMyYTRcdWIzYzRcdWNmZTBcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWM4MDFcdWM3NDAgXHViZTQ0XHVkMmI4XHViOTdjIFx1ZDFhMFx1YWUwMFx1YzJkY1x1Y2YxY1x1YzExYyBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNTg5XHVhY2ZjIFx1YzVmNCwgXHVhZGY4XHViOWFjXHVhY2UwIDMqM1x1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWFkNmNcdWFjMDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDFjIDFcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzlkZFx1YzIxOFx1YWMxY1x1YWMwMCBcdWI0MThcdWFjOGMgXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzgxY1x1YjI5NCAzXHViYzg4IFx1YjljY1x1YzVkMCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDgwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbjAwMCAwMDAgMDAwXHJcbjAwMSAwMDAgMTAwXHJcbjAwMSAwMDAgMTAwXHJcblxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG5cclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDA8XC9wcmU+XHJcblxyXG48cD5cdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwIFx1ZDM3Y1x1Yzk5MFx1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWQzN2NcdWM5OTBcdWM3NDQgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1ZDFhMFx1YWUwMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1YzU0NFx1ZDY0OSBcdWJjODhcdWM5ZjggXHVjOTA0IFx1YWU0Y1x1YzljMCBcdWJjMTRcdWM3NzRcdWIxMDhcdWI5YWMgXHVjMmE0XHViM2M0XHVjZmUwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YmMxNFx1Yzc3NFx1YjEwOFx1YjlhYyBcdWMyYTRcdWIzYzRcdWNmZTBcdWI5N2MgXHVkNDgwXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1ZDFhMFx1YWUwMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWQxYTBcdWFlMDBcdWM3NzRcdWI3ODAgMC0mZ3Q7MSwgMS0mZ3Q7MFx1YzczY1x1Yjg1YyBcdWJjMTRcdWFmYjhcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNTkyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpbmFyeSBTdWRva3UiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huJiMzOTtzIGNvd3MgbGlrZSB0byBwbGF5IGFuIGludGVyZXN0aW5nIHZhcmlhbnQgb2YgdGhlIHBvcHVsYXIgZ2FtZSBvZiAmcXVvdDtTdWRva3UmcXVvdDsuICZuYnNwO1RoZWlyIHZlcnNpb24gaW52b2x2ZXMgYSA5IHggOSBncmlkIG9mIDMgeCAzIHN1YmdyaWRzLCBqdXN0IGxpa2UgcmVndWxhciBTdWRva3UuICZuYnNwO1RoZSBjb3dzJiMzOTsgdmVyc2lvbiwgaG93ZXZlciwgdXNlcyBvbmx5IGJpbmFyeSBkaWdpdHM6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjAwMCAwMDAgMDAwXHJcbjAwMSAwMDAgMTAwXHJcbjAwMCAwMDAgMDAwXHJcblxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMTExIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG5cclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuPFwvcHJlPlxyXG5cclxuPHA+VGhlIGdvYWwgb2YgYmluYXJ5IFN1ZG9rdSBpcyB0byB0b2dnbGUgYXMgZmV3IGJpdHMgYXMgcG9zc2libGUgc28gdGhhdCBlYWNoIG9mIHRoZSBuaW5lIHJvd3MsIGVhY2ggb2YgdGhlIG5pbmUgY29sdW1ucywgYW5kIGVhY2ggb2YgdGhlIG5pbmUgMyB4IDMgc3ViZ3JpZHMgaGFzIGV2ZW4gcGFyaXR5IChpLmUuLCBjb250YWlucyBhbiBldmVuIG51bWJlciBvZiAxcykuICZuYnNwO0ZvciB0aGUgZXhhbXBsZSBhYm92ZSwgYSBzZXQgb2YgMyB0b2dnbGVzIGdpdmVzIGEgdmFsaWQgc29sdXRpb246PFwvcD5cclxuXHJcbjxwcmU+XHJcbjAwMCAwMDAgMDAwXHJcbjAwMSAwMDAgMTAwXHJcbjAwMSAwMDAgMTAwXHJcblxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMTEwIDAwMFxyXG4wMDAgMDAwIDAwMFxyXG5cclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuMDAwIDAwMCAwMDBcclxuPFwvcHJlPlxyXG5cclxuPHA+R2l2ZW4gdGhlIGluaXRpYWwgc3RhdGUgb2YgYSBiaW5hcnkgU3Vkb2t1IGJvYXJkLCBwbGVhc2UgaGVscCB0aGUgY293cyBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRvZ2dsZXMgcmVxdWlyZWQgdG8gc29sdmUgaXQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmVzIDEuLjk6IEVhY2ggbGluZSBjb250YWlucyBhIDktZGlnaXQgYmluYXJ5IHN0cmluZyBjb3JyZXNwb25kaW5nIHRvIG9uZSByb3cgb2YgdGhlIGluaXRpYWwgZ2FtZSBib2FyZC48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBtaW5pbXVtIG51bWJlciBvZiB0b2dnbGVzIHJlcXVpcmVkIHRvIG1ha2UgZXZlcnkgcm93LCBjb2x1bW4sIGFuZCBzdWJncmlkIGhhdmUgZXZlbiBwYXJpdHkuPFwvcD5cclxuIiwiaGludCI6IjxwPlRocmVlIHRvZ2dsZXMgc3VmZmljZSB0byBzb2x2ZSB0aGUgcHV6emxlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO November 2011 Contest > Gold 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: cheetose