[백준] 1581번 '락스타 락동호' - Java

https://www.acmicpc.net/problem/1581

---

문제

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int ff = Integer.valueOf(st.nextToken());
		int fs = Integer.valueOf(st.nextToken());
		int sf = Integer.valueOf(st.nextToken());
		int ss = Integer.valueOf(st.nextToken());
		
		System.out.println(solution(ff, fs, sf, ss));
	}
	
	public static int solution(int ff, int fs, int sf, int ss) {
		if(ff == 0 && fs == 0) return ss + Math.min(sf, 1);
		if(fs == 0) return ff;
		if(fs > sf) return 2*sf + 1 + ss + ff;
		else return 2*fs + ss + ff;
	}
}

 

 

첫 번째 if 문: FF나 FS가 존재하지 않는다면, SF, SS만 있을 것이고, SS를 모두 쓴 다음 SF는 하나만 들어가던가, 없다면 0개가 들어가게 될 것 입니다. 1과 SF 중 더 작은 것을 더하게 합니다.

 

두 번째 if 문: FS가 0이라면 FF가 제일 앞에 올 수 밖에 없습니다. FF 뒤에 올 수 있는 것은 FF와 FS말고는 없으므로 FF가 반환됩니다.

 

세 번째 if 문: 위 두 가지 경우가 아니라면, 

- FF가 젤 앞에 올 수 있다

- FS와 SF가 반복된다.

- SS가 있을 수 있다

 

인데, FS와 SF가 반복되는 경우로 인해 FF와 SS의 위치는 상관하지 않아도 됩니다. 왜냐하면 FS - SF 순이라고 했을 때, FF를 맨 앞에 두면 되고, SF다음에 FF를 둬도 됩니다. 마찬가지로, FS와 SF 사이에 SS는 아무렇게나 배치해도 되기 때문에 SS를 그대로 더해도 되죠. 하지만, FS와 SF의 개수는 짝을 맞추어야 하기 때문에 더 작은 쪽을 선택하게 됩니다. FS-SF 순으로 배치해야하므로, FS>SF인 경우에는 FS가 하나 더 올 수 있으니 1을 더 더해주고, 반대의 경우에는 SF는 따로 하나 더 못 쓰기 때문에 1을 더하지 않습니다.

public static int solution(int ff, int fs, int sf, int ss) {
		if(ff == 0 && fs == 0) return ss + Math.min(sf, 1);
		if(fs == 0) return ff;
		if(fs > sf) return 2*sf + 1 + ss + ff;
		else return 2*fs + ss + ff;
	}

 

---

후기

기존에 제가 하려던 방식은 DFS를 사용하는 방식이었습니다.

 

위와 같이 규칙이 있길래 이진 트리를 사용하는 줄 알고 두근두근 하면서 코드를 짜본 결과...

 

이렇게 하면 DFS에서 돌아갈 때에 윗단으로 수정 전의 배열을 넘겨줘야 하는데 자바는 call by reference 형식이기때문에 쉽지 않더군요.. 일반 배열도, arraylist도, hashmap도 모두 그렇다고 하니 더 이상 방법이 없었습니다.

 

그러다가 코드를 서치해봤고.. 정말.. 단순하게 풀리더라고요.

단순하게 풀려서 더 어려운 문제가 아니었나 싶습니다. 풀이를 본 다음에 처음에는 문제가 참 안 좋다고 생각했지만, 계속 생각해보니까 단순하게 생각한다는 것이 어려운 이유가 아직 많은 문제를 접해보지 못했기 때문이라고 깨달았습니다.

 

그렇지만 전 저의 방식대로도 한 번 풀어보고 싶었기 때문에, 배열을 넘겨주는 대신에 객체 안에 배열에 들어가는 ff, fs, sf, ss를 int 형으로 변수를 4개 씩이나 넣어서! 풀어보았습니다...

 

예제 1~3까지는 잘 돌아가지만 4에서는 무한 루프에 빠졌습니다. 조건문을 때려넣게 되면서 코드가 좋지 못한 것 같지만, 1~3을 저 혼자 힘으로 해냈다는 것이 뿌듯하여 올려봅니다.

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class BOJ1581 {
	static class Node {
		int data, ff, fs, sf, ss;
		int left, right, cnt;
		public Node(int data, int ff, int fs, int sf, int ss, int cnt) {
			this.data = data;
			this.ff = ff;
			this.fs = fs;
			this.sf = sf;
			this.ss = ss;
			this.cnt = cnt;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int ff, fs, sf, ss = 0;
		int start = 0;
		
		ff = Integer.valueOf(st.nextToken());
		fs = Integer.valueOf(st.nextToken());
		sf = Integer.valueOf(st.nextToken());
		ss = Integer.valueOf(st.nextToken());
		
		if(ff > 0 || fs > 0) start = 0;
		else start = 2;
		for(int i=start; i<=start+1; i++) {
			DFS(i, ff, fs, sf, ss);
		}
		
		System.out.println("ans: " + ans);
	}
	
	public static int ans = 0;
	public static void DFS(int data, int ff, int fs, int sf, int ss) {
		
		Node node = new Node(data, ff, fs, sf, ss, 1);
		
		Stack<Node> s = new Stack<>();
		s.push(node);
		
		while(!s.isEmpty()) {
			
			Node curr = s.pop();
			System.out.println("현재 탐색: " + curr.data);
			System.out.println("ff:" + curr.ff + " fs:" + curr.fs + " sf:" + curr.sf + " ss:" + curr.ss);
			
			
			if(curr.data == 0 && curr.ff > 0) {
				curr.left = 0;
				curr.right = 1;
				curr.ff -= 1;
				
				if(curr.ff > 0 || curr.fs > 0) {
					curr.cnt += 1;
					s.push(new Node(curr.left, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					s.push(new Node(curr.right, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					
				} else {
					if(ans < curr.cnt) ans = curr.cnt;
				}
			} else if(curr.data == 1 && curr.fs > 0) {
				curr.left = 2;
				curr.right = 3;
				curr.fs -= 1;
				
				if(curr.sf > 0 || curr.ss > 0) {
					curr.cnt += 1;
					s.push(new Node(curr.left, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					s.push(new Node(curr.right, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					
				} else {
					if(ans < curr.cnt) ans = curr.cnt;
				}
			} else if(curr.data == 2 && curr.sf > 0) {
				curr.left = 0;
				curr.right = 1;
				curr.sf -= 1;
				
				if(curr.ff > 0 || curr.fs > 0) {
					curr.cnt += 1;
					s.push(new Node(curr.left, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					s.push(new Node(curr.right, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					
				} else {
					if(ans < curr.cnt) ans = curr.cnt;
				}
			} else if(curr.data == 3 && curr.ss > 0) {
				curr.left = 2;
				curr.right = 3;
				curr.ss -= 1;
				
				if(curr.sf > 0 || curr.ss > 0) {
					curr.cnt += 1;
					s.push(new Node(curr.left, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					s.push(new Node(curr.right, curr.ff, curr.fs, curr.sf, curr.ss, curr.cnt));
					
				} else {
					if(ans < curr.cnt) ans = curr.cnt;
				}
			}
			System.out.println("cnt" + curr.cnt);
			
		}
		
		
	}
}

 

혹시 고수님들이 계시다면 무한루프에 빠지는 이유를 댓글로 알려주시면 감사하겠습니다!!