1819번 - 불끄기 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 28 | 14 | 12 | 48.000% |
문제
상근이의 집에는 전구가 L개 있다. 각 전구를 켜고 끌 수 있는 스위치는 일렬로 늘어서있다. 전구가 켜진 상태에서 스위치를 누르면 꺼지고, 꺼진 상태에서 누르면 켜진다.
매일 밤, 잠을 자기 전에 상근이는 전구를 모두 끈다. 모든 스위치를 한 번씩 눌러 전구를 끄는 일은 시간이 오래걸린다.
불을 켜고 끄는 일을 조금 더 편하게 하기 위해 상근이는 스위치를 편하게 누를 수 있는 장치를 발명했다. 장치는 T개의 슬롯이 일렬로 놓여져있다. 일부 슬롯에는 스위치 버튼을 누를 수 있는 막대가 꽂혀있고, 나머지 슬롯은 비어있다. 예를 들어, 장치에 슬롯이 4개 있고, 1, 2, 4번째 슬롯에 막대가 꽂혀있으면, 이를 '1101'로 표현할 수 있다.
위의 장치로 L개의 스위치 중 가장 왼쪽 스위치를 누르면, 1, 2, 4번 스위치를 누를 수 있고, 그 전구의 상태가 변하게 된다. 3번 슬롯은 비어있기 때문에, 3번 전구는 변하지 않는다. 즉, 가장 왼쪽에 있는 슬롯을 기준으로 i번째 스위치를 누른다면 i, i+1, ..., i+T-1번째 스위치 중 막대가 꽂힌 슬롯에 대응되는 스위치의 전구가 변하게 된다. 단, T개의 모든 슬롯이 스위치와 대응되어야 한다. 즉, 스위치 바깥으로 슬롯이 나가면 안 된다.
현재 스위치의 상태와 상근이가 발명한 슬롯의 상태가 주어졌을 때, 불이 켜진 상태를 최소로 하려면 장치로 슬롯을 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 L (3 ≤ L ≤ 50)과 T (1 ≤ T ≤ 7)가 주어진다. 다음 줄에 길이가 L인 문자열이 주어진다. 1은 i번째 전구가 켜진 상태, 0은 꺼진 상태이다. 세 번째 줄에는 길이가 T인 문자열이 주어진다. 0은 빈 슬롯, 1은 막대가 꽂힌 슬롯이다.
출력
첫째 줄에 최소의 불이 켜진 상태를 만들기 위해 슬롯으로 눌러야할 등불 순서의 개수 K를 출력한다. 그 다음 K줄에는 눌러야 하는 스위치를 순서대로 출력한다. 슬롯으로 누르는 가장 왼쪽 스위치의 번호를 출력한다. (장치를 회전시킬 수는 없다) K는 1000보다 작거나 같아야 한다.
예제 입력 1
10 4 1111111111 1101
예제 출력 1
5 3 1 4 7 6
힌트
1111111111초기 상태11001011113-6번 불을 슬롯으로 누른 후00011011111-4번 불을 슬롯으로 누른 후00000001114-7번 불을 슬롯으로 누른 후00000010107-10번 불을 슬롯으로 누른 후00000100006-9번 불을 슬롯으로 누른 후
최종 1개의 불이 켜진 상태가 되고 모든 불을 끄는 해는 존재하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호