[Algorithm] ๐์๊ณ ๋ง์ถ๊ธฐ
1. ๋ฌธ์ ํด์
16๊ฐ์ ์๊ณ๊ฐ ์กด์ฌํ๊ณ ๋ชจ๋ 12์๋ก ๋ง์ถฐ์ผํจ
๊ฐ ์๊ณ๋ค์ ํ๋์ ๋ฒํผ์ ์ฐ๊ฒฐ๋์ด ์์ด์ ๋ฒํผ์ ํ ๋ฒ ๋๋ฅด๋ฉด 3์๊ฐ ํ๋ก ์ด๋ํจ
10๋ฒ ์ด๋ด์ ์๊ณ ๋ง์ถ๊ธฐ
์ ๋ ฅ
C(ํ ์คํธ ์ผ์ด์ค), 16๊ฐ ์๊ณ์ ์๊ฐ
์ถ๋ ฅ
12์๋ก ๋ง์ถ๊ธฐ ์ํด ๋ฒํผ์ ๋๋ฅด๋ ์ต์ ํ์ (10ํ ์ดํ)
2. ์์ด๋์ด
๐ก ํ ๊ฐ์ ์ค์์น๋ 4๋ฒ ์ด์ ๋๋ฅด์ง ์์ (๋ค์ ์์ํ๋ก ๋ณต๊ตฌ)
๐ก ์ค์์น์ ์ฐ๊ฒฐ๋์ด ์๋ ์๊ณ๋ฅผ ๋ฐฐ์ด๋ก ์ ์ฅํด์ ์ด์ฉ
๐ก ์ฌ๊ทํจ์ ์ฌ์ฉํ์ฌ ๊ฐ๊ฐ์ ์ค์์น๋ฅผ 0-3๋ฒ๊น์ง ๋๋ฌ๋ณด๊ณ ๊ฐ์ฅ ์์ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ์ ๋ฃ์
3. ํ์ด
1) ์ค์์น์ ์ฐ๊ฒฐ๋์ด ์๋ ์๊ณ๋ฅผ ๋ฐฐ์ด๋ก ์ ์ธ
static int linked[][] = {
{1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1},
{1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,1,1,0,1,0,1,0,0,0},
{1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1},
{0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1},
{0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0}
};
2) ๊ฐ๊ฐ์ ์ค์์น 0-3๋ฒ ๋๋ฌ๋ณด๊ณ , ret์ ์์ ๊ฐ ์ ์ฅ
int ret = INF;
for(int i=0; i<4; i++) {
ret = Math.min(ret, i+solve(clocks,swtch+1));
push(clocks,swtch);
}
4. ์ฝ๋
import java.util.*;
public class ClockSync {
static int INF = 9999;
static int SWITCH = 10;
static int CLOCK = 16;
static int linked[][] = {
{1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,1,0,1,0,1,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,1,0,0,0,1,1},
{1,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,1,1,0,1,0,1,0,0,0},
{1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,1},
{0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,1,1,0,1,0,0,0,0,0,0,1,1},
{0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0},
{0,0,0,1,1,1,0,0,0,1,0,0,0,1,0,0}
};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int c = sc.nextInt();
int clocks[] = new int[CLOCK];
int result[] = new int[c];
for(int i=0; i<c; i++) {
for(int j=0; j<CLOCK; j++) {
clocks[j] = sc.nextInt();
}
result[i] = solve(clocks,0);
if(result[i] == INF)
result[i] = -1;
}
for(int i=0; i<c; i++)
System.out.println(result[i]);
}
public static boolean areAligned(int clocks[]) {
for(int i=0; i<CLOCK; i++) {
if(clocks[i] != 12)
return false;
}
return true;
}
public static void push(int clocks[], int swtch) {
for(int clock=0; clock<CLOCK; clock++) {
if(linked[swtch][clock] == 1) {
clocks[clock] += 3;
if(clocks[clock] == 15)
clocks[clock] = 3;
}
}
}
public static int solve(int clocks[], int swtch) {
if(swtch == SWITCH)
return areAligned(clocks) ? 0:INF;
int ret = INF;
for(int i=0; i<4; i++) {
ret = Math.min(ret, i+solve(clocks,swtch+1));
push(clocks,swtch);
}
return ret;
}
}
5. ๊ฒฐ๊ณผ
์ฑ๊ณต!..
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ([Algorithm] ๐์๊ณ ๋ง์ถ๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kha0318/Algorithm-์๊ณ-๋ง์ถ๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค