https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN

---

문제 설명

원재가 컴퓨터를 만지다가 실수를 저지르고 말았다. 메모리가 초기화된 것이다.

다행히 원래 메모리가 무슨 값이었는지 알고 있었던 원재는 바로 원래 값으로 되돌리려고 했으나 메모리 값을 바꿀 때 또 문제가 생겼다.

메모리 bit중 하나를 골라 0인지 1인지 결정하면 해당 값이 메모리의 끝까지 덮어씌우는 것이다.

예를 들어 지금 메모리 값이 0100이고, 3번째 bit를 골라 1로 설정하면 0111이 된다.

원래 상태가 주어질 때 초기화 상태 (모든 bit가 0) 에서 원래 상태로 돌아가는데 최소 몇 번이나 고쳐야 하는지 계산해보자.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 메모리의 원래 값이 주어진다.

메모리의 길이는 1이상 50이하이다.

[출력]

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

초기값(모든bit가 0)에서 원래 값으로 복구하기 위한 최소 수정 횟수를 출력한다.

---

풀이

import java.io.*;

public class S1289_원재의메모리복구하기 {
	static String memory; 
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			memory = br.readLine();
			String firstMemory = memory.replace('1', '0'); //초기메모리
			System.out.printf("#%d %d", t, fix(firstMemory, 0, 0));
		}
	}
	/**
	 * @param mem 현재 고치고 있는 메모리
	 * @param idx 지금 재귀에서 가리키고 있는 memory의 자리수
	 * @param turn 고친 횟수
	 * */
	static int fix(String mem, int idx, int turn){
		//현재 자리수에서 숫자를 고칠까 말까 정하기
		//만약 원래 메모리랑 지금 메모리랑 자리수의 숫자가 다르면 그 숫자로 바꾸기
		if(memory.charAt(idx) != mem.charAt(idx)) {
			if(memory.charAt(idx)=='0') { //원래 지금 자리수 숫자가 0이어야 되면
				// 예를들어 1010인데 지금 1111이면, 1+000해야 함
				// idx전까지의 문자열 떼고, idx부터의 문자열은 전부 0으로 변경
				mem = mem.substring(0, idx) + mem.substring(idx).replace('1', '0');
			}
			else { //원래 지금 자리수 숫자가 1이어야 되면
				// 1011 vs 1000 => 10+11
				mem = mem.substring(0, idx) + mem.substring(idx).replace('0', '1');
			}
			turn++; //수정 횟수 증가
		}
		//만약 목표숫자 달성 시 재귀 종료
		if(mem.equals(memory)) return turn;
		//목표숫자 미달성시 다음자리 숫자 정하기
		return fix(mem, ++idx, turn);
	}

}

재귀로 풀었다.
사실 반복문으로 하는 게 더 낫다.

현재 idx을 인덱스로 하는 원본 메모리와 원재 메모리의 값을 비교한다

값이 다르면 스위치 값을 변경하고 그 뒤에 숫자도 다 바꾼다

목표숫자 달성시 재귀 종료

---

결과