☌

[KAKURO1] Kakuro I

개발이야기/알고스팟2022. 1. 6. 11:44

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/KAKURO1

 

algospot.com :: KAKURO1

Kakuro I 문제 정보 문제 카쿠로는 흔히 십자말풀이 수학 버전이라고 불리는 논리 퍼즐이다. 카쿠로는 위와 같이 생긴 정사각형의 게임판을 가지고 하는 퍼즐로, 이 게임판의 각 칸은 흰 칸이거나,

www.algospot.com

 

풀이입니다. 🤔

 

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
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Answer> answers = new ArrayList<>();
        int[][] board = new int[20][20], directions = new int[][] {{0, 1}, {1, 0}};
 
        int cases = scanner.nextInt();
        System.out.println(cases);
        while (cases-- > 0) {
            int n = scanner.nextInt();
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    board[i][j] = scanner.nextInt();
                }
            }
            for (int i = 0, len = directions.length; i < len; ++i) {
                int[] direction = directions[i];
                for (int j = 0; j < n; ++j) {
                    for (int k = 0; k < n; ++k) {
                        if (board[j][k] != 0) continue;
 
                        int ret = 0, y = j + direction[0], x = k + direction[1];
                        while (y < n && x < n && board[y][x] != 0) {
                            ret += board[y][x];
                            y += direction[0];
                            x += direction[1];
                        }
                        if (ret != 0) answers.add(new Answer(j + 1, k + 1, i, ret));
                    }
                }
            }
 
            System.out.println(n);
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    System.out.printf("%d%c", (board[i][j] == 0) ? 0 : 1, (j == n - 1) ? '\n' : ' ');
                }
            }
            System.out.println(answers.size());
            for (Answer answer : answers) System.out.println(answer);
            answers.clear();
        }
    }
 
    private static final class Answer {
        final int y, x, direction, value;
 
        public Answer(int y, int x, int direction, int value) {
            this.y = y;
            this.x = x;
            this.direction = direction;
            this.value = value;
        }
 
        @Override
        public String toString() {
            return String.format("%d %d %d %d", y, x, direction, value);
        }
    }
}
 cs

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[ENCODING] Encoding  (0) 2022.01.06
[CANDLESTICK] Candlestick Charts  (0) 2022.01.06
[FESTIVAL] 록 페스티벌  (0) 2022.01.06
[NOTE] Note  (0) 2022.01.06
[MAGICPOWER] 마력  (0) 2022.01.05
Posted by N'
,

[FESTIVAL] 록 페스티벌

개발이야기/알고스팟2022. 1. 6. 10:49

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/FESTIVAL

 

algospot.com :: FESTIVAL

록 페스티벌 문제 정보 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체

www.algospot.com

 

풀이입니다. 🤔

 

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
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
 
        int[][] caches = new int[1000][1000];
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt(), l = scanner.nextInt();
            for (int i = 0; i < n; ++i) {
                caches[0][i] = (i == 0) ? scanner.nextInt() : caches[0][i - 1] + scanner.nextInt();
            }
 
            for (int i = 1; i < n; ++i) {
                for (int j = i; j < n; ++j) {
                    // i일부터 (j-i+1)일 연속 공연했을 때의 총 비용
                    caches[i][j] = caches[i - 1][j] - caches[i - 1][i - 1];
                }
            }
 
            double ret = Double.MAX_VALUE;
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    int len = j - i + 1;
                    if (len >= l) ret = Math.min(ret, ((double) caches[i][j]) / len);
                }
            }
 
            System.out.printf("%.8f\n", ret);
        }
    }
}
 cs

 

최소 평균 비용을 알기 위해, 모든 경우의 수를 탐색해 보는 것을 고민해봤습니다. 

i일부터 연속 (n-i+1)일 간의 총 비용을 구한 뒤, 최소 평균을 구하도록 되어 있습니다. 

해당 요구사항은 파스칼의 삼각형과 같이 처음부터 모든 덧셈을 하는 것이 아닌 일련의 점화식을 만들면 제곱 시간안에 구해볼 수 있습니다.


이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[CANDLESTICK] Candlestick Charts  (0) 2022.01.06
[KAKURO1] Kakuro I  (0) 2022.01.06
[NOTE] Note  (0) 2022.01.06
[MAGICPOWER] 마력  (0) 2022.01.05
[DECODE] Decoding  (0) 2022.01.05
Posted by N'
,

[NOTE] Note

개발이야기/알고스팟2022. 1. 6. 10:33

C 로 풀어보는 알고리즘입니다. 📖 

(이번 문제는 Java 를 이용할 시, input 과정 중 시간초과를 발생시키는 요소가 있는 것 같아 보입니다.)
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/NOTE

 

algospot.com :: NOTE

Note 문제 정보 문제 C major scale consists of 8 tones: c d e f g a b C. For this task we number the notes using numbers 1 through 8. The scale can be played ascending, from 1 to 8, descending, from 8 to 1, or mixed. Write a program that, given the se

www.algospot.com


풀이입니다. 🤔

 

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
#include <stdio.h>
#define ASC 0
#define DESC 1
#define MIX 2
 
int main()
{
    int oldValue, newValue, ret = MIX;
    for (int i = 0; i < 8; ++i)
    {
        scanf("%d", &newValue);
        if (i == 0)
        {
            if (newValue == 1 || newValue == 8)
            {
                ret = (newValue == 1) ? ASC : DESC;
                oldValue = newValue;
            }
        }
        else
        {
            switch (ret)
            {
            case ASC:
                ret = (newValue - oldValue == 1) ? ASC : MIX;
                break;
 
            case DESC:
                ret = (oldValue - newValue == 1) ? DESC : MIX;
                break;
            }
 
            oldValue = newValue;
        }
    }
 
    switch (ret)
    {
    case ASC:
        printf("ascending\n");
        break;
 
    case DESC:
        printf("descending\n");
        break;
 
    case MIX:
        printf("mixed\n");
        break;
    }
 
    return 0;
}
 cs

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[KAKURO1] Kakuro I  (0) 2022.01.06
[FESTIVAL] 록 페스티벌  (0) 2022.01.06
[MAGICPOWER] 마력  (0) 2022.01.05
[DECODE] Decoding  (0) 2022.01.05
[FIX] 문제 순서는 난이도 순이 아닙니다  (0) 2022.01.05
Posted by N'
,
Daum / Designed by i2i Labs

티스토리툴바