Posted Updated algorithm7 minutes read (About 1084 words)

백준 20055 컨베이어 벨트 위의 로봇 JAVA

문제

링크 : https://www.acmicpc.net/problem/20055

길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다.

img

벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 Ai이다. 위의 그림에서 1번 칸이 있는 위치를 “올리는 위치“, N번 칸이 있는 위치를 “내리는 위치“라고 한다.

컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올리는 위치에만 올릴 수 있다. 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다. 로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다. 로봇을 올리는 위치에 올리거나 로봇이 어떤 칸으로 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다.

컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.

  1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
  2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
    1. 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
  3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
  4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.

종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.

풀이

문제를 이해를 조심스럽게 해야하는 문제

우선 맨앞에 추가한다던가 맨뒤에 있는 것을 뺀다거나 해야해서 Deque 자료구조를 사용하는 것이 편함

그 뒤에는 일련의 과정을 시키는대로 구현하면 됨

  1. rotation
    1. 위 컨베이어 벨트에서 맨 마지막 로봇을 아래 컨베이어 벨트로 내림
    2. 아래 컨베이어 벨트의 첫번째 로봇을 위 컨베이어 벨트로 올림
  2. move
    1. 로봇이 없고 등등 위 컨베이어 벨트에서 마지막에 가까운 로봇을 먼저 조건에 맞으면 이동시킴
  3. 로봇을 올릴 수 있으면 올린다
  4. 조건에 맞으면 종료 아니면 1번으로 돌아가 반복

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

class Pair
{
    Integer key;
    Integer value;

    public Pair(int key,int value)
    {
        this.key = key;
        this.value = value;
    }

    public Integer getKey()
    {
        return this.key;
    }
    public Integer getValue()
    {
        return this.value;
    }

    public void setKey(int key)
    {
        this.key = key;
    }
    public void setValue(int val)
    {
        this.value = val; 
    }
}


class Main
{
    static int N,K;
    static Deque<Pair> upBelt = new ArrayDeque<>();
    static Deque<Integer> downBelt = new ArrayDeque<>();
    static Scanner sc;
    static int countK = 0;

    static void inputFromIO()
    {
        sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        for(int i=0;i<N;i++)
        {  
            upBelt.add(new Pair(sc.nextInt(),0));
        }
        for(int i=0;i<N;i++)
        {
            downBelt.addFirst(sc.nextInt());
        }
    }
    //회전할때는 내리는 위치에 있는애만 내리고
    //올리는 애는 안올림
    static void rotation()
    {
        int downFirst = downBelt.pollFirst();
        Pair upLast = upBelt.pollLast();
        int upLastVal = upLast.getKey();
        downBelt.addLast(upLastVal);
        upBelt.addFirst(new Pair(downFirst,0));
        Pair afterUpLast = upBelt.getLast();
        if(afterUpLast.value == 1)
        {
            afterUpLast.value = 0;
        }
    }

    static void robotMove()
    {
        Iterator<Pair> iter = upBelt.descendingIterator();
        //맨마지막은 어차피 못움직임(내리는 위치니까)
        Pair prev = iter.next();
        int prevRobot = prev.getValue();
        for(; iter.hasNext();)
        {
            Pair curBelt = iter.next();
            if(prevRobot == 0 && prev.getKey() > 0 && curBelt.getValue() == 1) 
            {
                prev.setKey(prev.getKey()-1);
                curBelt.setValue(0); 
                prev.setValue(1);
                if(prev.getKey() == 0)
                {
                    countK++;
                }
            }
            prev = curBelt;
            prevRobot = curBelt.getValue();

        }
        prevRobot = upBelt.getLast().value;
        if(prevRobot == 1)
        {
            upBelt.getLast().value = 0;
        }
    }

    static void robotAdd()
    {
        Pair first = upBelt.getFirst();
        if(first.key >= 1)
        {
            first.setValue(1);
            first.key--;
            if(first.key== 0)
            {
                countK++;
            }
        }
    }

    static void solve()
    {  
        int level = 0;
        while(countK < K)
        {
            //System.out.println("***********\nbefore");
            //printAll();
            rotation();
            //System.out.println("\nafter");
            //printAll();
            robotMove();
            //System.out.println("\nafter robot move");
            //printAll();
            robotAdd();
            //System.out.println("\nafter robot add");
            //printAll();
            level++;
            //System.out.println();
            //sc.next();
            //countK = printAll();

        }
        System.out.println(level);
    }
    

    public static void main(String args[])
    {
        inputFromIO();
        solve();
    }
}

메모

문제 이해를 잘 못해서 한번 꼬였고 두번째 구현에서도 조금 시간이 걸렸음

구현력이 좀 떨어진다

Posted Updated algorithm6 minutes read (About 903 words)

백준 14889 스타트와 링크 JAVA

문제

링크 : https://www.acmicpc.net/problem/14889

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

i\j 1 2 3 4
1 1 2 3
2 4 5 6
3 7 1 2
4 3 4 5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

  • 스타트 팀: S12 + S21 = 1 + 4 = 5
  • 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

  • 스타트 팀: S13 + S31 = 2 + 7 = 9
  • 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

풀이

모든 경우의 수를 돌면서 최소 차이의 경우를 찾아내면 되는 문제

문제는 어떻게 구현할 것이냐인데 나도 이런 문제에서 모든 경우의 수를 어떻게 구하지? 하는 생각에

풀지 못하고 코드를 참조했었는데 지금와서는 모든 경우의 수를 구한다 -> 백트래킹, DFS, 비트마스킹을 사용하면 어느정도 해소된다 생각한다.

어쨌건 풀이자체는 간단하다 백트래킹으로 모든 경우의 수에서 visit이면 start, !visit이면 link팀으로 생각하고

이 때 차이를 계산하고 차이가 적은 점수로 갱신해주면 된다.

풀이는 간단하지만 구현상에서 언제 visit을 false로 할 것인가 라던가 조금 섬세함이 필요한 문제

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.util.Scanner;

public class Main
{
    static int MAX = 21;
    static int arr[][];
    static boolean visit[];
    static int N = 0;
    static int ans = 987654321;

    static int getScore(int array[])
    {
        int result = 0;
        int len = N/2;
        for(int i=1;i<=len;i++)
        {
            for(int j=i+1;j<=len;j++)
            {
                result += arr[array[i]][array[j]];
                result += arr[array[j]][array[i]];
            }
        }
        return result;
    }
    
    static void setDiff()
    {
        int start[] = new int[N/2+1];
        int link[] = new int[N/2+1];
        int startIdx = 1;
        int linkIdx = 1;
        for(int i=1;i<=N;i++)
        {
            if(visit[i])
            {
                start[startIdx++]= i;
            }
            else
            {
                link[linkIdx++]= i;
            }
        }
        int startScore = getScore(start);
        int linkScore = getScore(link);
        int result = Math.abs(startScore - linkScore);
        if(result < ans)
        {
            ans = result;
        }
    }

    static void dfs(int v,int count)
    {
        if(count == N/2)
        {
            setDiff();
        }
        else
        {
            for(int i=v+1;i<=N;i++)
            {
                if(!visit[i])
                {
                    visit[i] = true;
                    dfs(i,count+1);
                }
            }
        }
        visit[v] = false;
    }   


    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();


        arr = new int[MAX][MAX];
        visit = new boolean[MAX];

        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=N;j++)
            {
                arr[i][j] = sc.nextInt();
            }
        }

        sc.close();
        dfs(0,0);
        System.out.println(ans);
    }


}

메모

모든 경우의 수를 생각해야한다(브루트 포스) -> 백트래킹,DFS 생각해볼만 함

Posted Updated algorithm4 minutes read (About 606 words)

programmers 12949 행렬의 곱셈

개요

요즘 블로그 글을 쓰는게 엄청 뜸했는데

기록이 정말정말 중요하다는 생각에 다시 열심히 써볼려고 함!

우선은 밀린 글부터 차근차근 써나갈 예정

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12913

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

풀이

이전에 밟은 땅의 점수를 의미하는 tmp 변수를 이용한다.

문제에서 이전에 밟은 땅은 연속적으로 밟을 수 없다고 하였으므로 이 부분 주의하여 이전에 밟지 않은 땅만 계산한다.

이전에 밟은 땅 점수 + 현재 밟은 땅의 점수를 계산하여 가능한 모든 경우의 수에 최대값을 계산하면 되는 문제

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {

    public String getNDigitNum(int n,int digit)
    {
        StringBuilder sb = new StringBuilder();
        int curNumber = n;
        if(curNumber == 0)
        {
            return "0";
        }
        while(curNumber > 0)
        {
            if(curNumber % digit < 10)
            {
                sb.append(curNumber % digit);
            }
            else
            {
                sb.append((char)(curNumber % digit - 10 + 'A'));
            }
            curNumber /= digit;
        }
        return sb.reverse().toString();
    }
    //0, 1, 1, 0, 1, 1, 1, 0, 0
    //digit,number,people,count
    public String solution(int n, int t, int m, int p) {
        String nDigitString;
        StringBuilder answerStrBuild = new StringBuilder();
        int curT = 1;
        int num=0;
        int countT = 0;
        while(true)
        {
            nDigitString = getNDigitNum(num++,n);
            for(int idx=0;idx<nDigitString.length();idx++)
            {
                if(curT == p)
                {
                    answerStrBuild.append(nDigitString.charAt(idx));
                    countT++;
                    if(countT == t)
                    {
                        return answerStrBuild.toString();
                    }
                }
                curT++;
                if(curT > m)
                {
                    curT = 1;
                }
            }
        }
    }
}

메모

문제를 잘못 이해해서 이전에 밟은 땅은 다시 안밟는다고 해석했는데 그럼 문제에 모순이 생기는데

어쨌건 해보자 해서 백트래킹으로 풀려고 했었던 기억이 남

문제에 모순이 생긴다 -> 문제를 잘못 이해한 것이므로 그냥 대충 넘어가면 안될 것 같다!

Posted Updated algorithm4 minutes read (About 640 words)

programmers 17687 [3차] n진수 게임

문제

N진수 게임
튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.

숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.
10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다.
이렇게 게임을 진행할 경우,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, …
순으로 숫자를 말하면 된다.

한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는
0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, …
순으로 숫자를 말하면 된다.

이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.

풀이

  • 입력받은 10진수를 n진수로 변환한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {

    public String getNDigitNum(int n,int digit)
    {
        StringBuilder sb = new StringBuilder();
        int curNumber = n;
        if(curNumber == 0)
        {
            return "0";
        }
        while(curNumber > 0)
        {
            if(curNumber % digit < 10)
            {
                sb.append(curNumber % digit);
            }
            else
            {
                sb.append((char)(curNumber % digit - 10 + 'A'));
            }
            curNumber /= digit;
        }
        return sb.reverse().toString();
    }
    //0, 1, 1, 0, 1, 1, 1, 0, 0
    //digit,number,people,count
    public String solution(int n, int t, int m, int p) {
        String nDigitString;
        StringBuilder answerStrBuild = new StringBuilder();
        int curT = 1;
        int num=0;
        int countT = 0;
        while(true)
        {
            nDigitString = getNDigitNum(num++,n);
            for(int idx=0;idx<nDigitString.length();idx++)
            {
                if(curT == p)
                {
                    answerStrBuild.append(nDigitString.charAt(idx));
                    countT++;
                    if(countT == t)
                    {
                        return answerStrBuild.toString();
                    }
                }
                curT++;
                if(curT > m)
                {
                    curT = 1;
                }
            }
        }
    }
}

10진수 -> n진수 변환

m진수 -> n진수 변환이 아닌 10진수 - > n진수 변환인 점 유의 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public String getNDigitNum(int n,int digit)
{
	StringBuilder sb = new StringBuilder();
	int curNumber = n;
	if(curNumber == 0)
	{
		return "0";
	}
	while(curNumber > 0)
	{
		if(curNumber % digit < 10)
		{
			sb.append(curNumber % digit);
		}
		else
		{
			sb.append((char)(curNumber % digit - 10 + 'A'));
		}
		curNumber /= digit;
	}
	return sb.reverse().toString();
}

n진수 변환 -> 10진수 변환

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static int nToTenDigit(String num, int N){

	char[] numArray = num.toCharArray();
	int ans = 0;
	for(int i=0;i < numArray.length;i++)
	{
		if(numArray[i] >= 'A')
		{
			//10진수 이상의 진수
			ans = ans * N + (numArray[i] - 'A' + 10);
		}
		else
		{
			//10진수 미만의 n
			ans = ans * N + (numArray[i] - '0');
		}
		
	}
}


메모

내가 직접 생각해서 구현한 방식은 비효율적이어서 인터넷에서 코드를 참조했다.

Follow

Categories

Recents

Archives

Tags

CRF3
algorithm72
book_report2
database1
java26
jpa1
pet project12
pet_project1
retrospect1
springboot3
web3
web pet project2
write3

Subscribe for updates

×