문제링크

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

풀이

합이 S라면 1부터 N까지 더하며 S가 넘지 않을때까지 반복한다.

input은 S(1 ≤ S ≤ 4,294,967,295)으로 40억이 넘어가기 때문에 long으로 사용해야 한다.

1부터 더해야 하기 때문에 idx를 1로 시작한다.

200을 예로 들었을 때, 아래의 코드는 sum = 210, idx = 21인 상태에서 if문에 걸리게 된다.

idx++이 된 부분에 대해서 한번 빼주고, sum이 초과되는 부분에서 한번 더 빼준다.

설명으로 하니 복잡한데 반복문 내에 idx와 sum을 찍어보면 아래와 같이 나온다.

//idx sum
1 1
2 3
3 6
...
19 190
20 210
나가!
19

후위연산자로 증가한 값을 하나 줄여주고, 반복문 내에서 sum이 초과한 이전의 숫자를 사용하기 위해 한번 더 빼준다.

따라서 idx를 -2 해주게 되는 것이다.

처음에 이것을 잡는데 시간이 오래 걸렸다.

그 외의 반례로는 input 1, output 1을 확인하기.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main{

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long S = Long.parseLong(br.readLine());

        //1부터 계속 더하면서 S가 넘지 않을때까지 반복
        long sum = 0;
        long idx = 1;
        while(true){
        	//System.out.print(idx +" ");
            sum += idx++;
            //System.out.println(sum);
            if(sum > S){
                //System.out.println("나가!");
                idx-=2;
                break;
            }
        }
        System.out.println(idx);
    }
}

그리디는 항상 접근이 어렵고 감을 잡으면 풀이는 쉬워지는 것 같다.

더 많이 풀어봐야지

문제 링크

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

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N, M;
	static char[][] map;

	static class Pos {
		int x, y, cnt, key;

		public Pos(int x, int y, int cnt, int key) {
			this.x = x;
			this.y = y;
			this.cnt = cnt;
			this.key = key;
		}	
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		map = new char[N][M];

		int startX = 0, startY = 0;
		String temp;
		for (int i = 0; i < N; i++) {
			temp = br.readLine();
			for (int j = 0; j < M; j++) {
				map[i][j] = temp.charAt(j);
				if (map[i][j] == '0') {
					startX = i; // 시작 위치 설정
					startY = j;
				}
			}
		} // end input

		bfs(startX, startY);

	}

	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	private static void bfs(int startX, int startY) {
		Queue<Pos> q = new ArrayDeque<>();
		boolean[][][] v = new boolean[64][N][M]; // a~f까지 키 주웠는지 확인 배열
		q.add(new Pos(startX, startY, 0, 0)); // 첫번째 출발 위치 넣음. 키는 아무것도 없음
		map[startX][startY] = '.';

		while (!q.isEmpty()) {
			Pos cur = q.poll();

			for (int d = 0; d < 4; d++) {
				int nx = cur.x + dr[d];
				int ny = cur.y + dc[d];

				if (!isRange(nx, ny) || map[nx][ny] == '#' || v[cur.key][nx][ny])
					continue; // 범위 벗어나거나, 벽이거나, 현재키로 방문했으면 다른방향
				
				if(map[nx][ny]=='1') {
					System.out.println(cur.cnt+1);
					return;
				}
				
				if (map[nx][ny] == '.') { // 갈 수 있으면 다음 방향 넣음
					v[cur.key][nx][ny] = true;
					q.add(new Pos(nx, ny, cur.cnt+1, cur.key));
				}
				if (map[nx][ny] >= 'a' && map[nx][ny] <= 'f') {// 소문자라면
					int gainKey = 1 << (map[nx][ny] - 'a');
					gainKey = cur.key | gainKey; // or 연산으로 현재 얻은 키 갱신

					if (!v[cur.key][nx][ny]) { //현재 키들로 방문하지 않았을 때 방문처리해줌 ->다시 갈 필요 없기 때문
						v[cur.key][nx][ny] = true;
						v[gainKey][nx][ny] = true;
						q.add(new Pos(nx, ny, cur.cnt + 1, gainKey));
					}
				}
				if (map[nx][ny] >= 'A' && map[nx][ny] <= 'F') {
					int checkKey = 1 << (map[nx][ny]-'A');
					if((cur.key & checkKey) > 0) { //키와 문의 대응이 1이상 존재한다면
						v[cur.key][nx][ny] = true;
						q.add(new Pos(nx, ny, cur.cnt+1, cur.key));
					}
				}

			}
		}
		System.out.println(-1);
		return;
	}

	private static boolean isRange(int x, int y) {
		if (x < 0 || y < 0 || x >= N || y >= M)
			return false;
		return true;
	}
}

bfs로 풀었는데 비트마스킹으로도 풀 수 있다!

문제 링크

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

접근 방법

1. 맵을 입력 받을 때 전체 인구수를 구한다
2. 경계선을 구한다
3. fifth배열에 경계선을 true로 표시한다.
4. 1~4 선거구 범위에 맞춰 popu 배열에 각 선거구의 인구수를 저장한다
5. 5번 선거구 = 전체 인구수 - popu배열 전체 합
6. popu 배열을 정렬해서 최대값과 최소값의 차이를 구해 전체 인구 차이의 최소값을 갱신한다.

1. 맵을 입력 받을 때 전체 인구수를 구한다

totalPopu = 0; //전체 인구수를 저장하기 위한 변수

map = new int[N + 1][N + 1];

for (int i = 1; i <= N; i++) {
	StringTokenizer tokens = new StringTokenizer(br.readLine());
	for (int j = 1; j <= N; j++) {
		map[i][j] = Integer.parseInt(tokens.nextToken());
		totalPopu += map[i][j]; //총 인구수를 구함
	}
}

경계선을 정하고 선거구 범위에 맞춰 인구수를 구한다면, 5번 선거구의 인구는 전체인구 - 1~4번 선거구 인구로 계산할 수 있다.

2. 경계선을 구한다.

• 기준점 (x, y)
• 경계의 길이 d1, d2

배열의 전체를 돌 x, y와 경계의 길이가 될 d1과 d2를 구한다. 4중 for문을 사용한다.

for (int x = 1; x <= N; x++) {
    for (int y = 1; y <= N; y++) {
        for (int d1 = 1; d1 <= N; d1++) {
            for (int d2 = 1; d2 <= N; d2++) {
				//3~6번 실행
            }
        }
    }
}//end 4 for

3. fifth 배열에 경계선을 true로 표시한다

문제에 주어진 경계선 조건은 다음과 같다

1. (x, y), (x+1, y-1), ..., (x+d1, y-d1)
2. (x, y), (x+1, y+1), ..., (x+d2, y+d2)
3. (x+d1, y-d1), (x+d1+1, y-d1+1), ... (x+d1+d2, y-d1+d2)
4. (x+d2, y+d2), (x+d2+1, y+d2-1), ..., (x+d2+d1, y+d2-d1)

이 경계선을 그대로 반복문에 적용한다.

for (int x = 1; x <= N; x++) {
    for (int y = 1; y <= N; y++) {
        for (int d1 = 1; d1 <= N; d1++) {
            for (int d2 = 1; d2 <= N; d2++) {

				//문제에 주어진 x, y, d1, d2의 조건
                //(d1, d2 ≥ 1, 1 ≤ x < x+d1+d2 ≤ N, 1 ≤ y-d1 < y < y+d2 ≤ N)
                if (x + d1 + d2 > N) continue;
                if (y - d1 < 1 || y + d2 > N) continue;

                popu = new int[5]; //1~5번 선거구의 인구수를 저장할 배열

                //5번 선거구의 경계선을 지역구 배열에 true 표시
                //각 지역구별로 다르게 범위를 구하면서 인구수 저장
                boolean[][] fifth = new boolean[N + 1][N + 1];
                //경계선 긋기
                for (int r = x, c = y; r <= x + d1; r++, c--)
                    fifth[r][c] = true;
                for (int r = x, c = y; r <= x + d2; r++, c++)
                    fifth[r][c] = true;
                for (int r = x + d1, c = y - d1; r <= x + d1 + d2; r++, c++)
                    fifth[r][c] = true;
                for (int r = x + d2, c = y + d2; r <= x + d2 + d1; r++, c--)
                    fifth[r][c] = true;

            }
        }
    }
}//end 4 for

위의 코드를 실행하면 다음과 같은 배열이 만들어지고, true가 5번 선거구의 경계선이 된다.

처음에 r, c를 2중 for문을 사용했더니 □ 모양의 경계선이 만들어졌다. r과 c를 동시에 증감시켜야 ◇ 모양으로 경계선이 생성된다.

4. 1~4 선거구 범위에 맞춰 popu 배열에 각 선거구의 인구수를 저장한다

선거구 범위

• 1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
• 2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
• 3번 선거구: x+d1 ≤ r ≤ N, 1 ≤ c < y-d1+d2
• 4번 선거구: x+d2 < r ≤ N, y-d1+d2 ≤ c ≤ N

한 행씩 읽으면서 1~4구역을 선거구 범위에 맞춰 읽는다. 한 행을 읽는 도중 경계선을 만난다면 다음 행으로 넘어간다.

1번과 3번 구역은 좌->우로 읽으면 되지만 2번과 4번 구역은 화살표와 같이 열의 끝에서 앞으로 읽어야 경계선을 만날 수 있다.

//1번 선거구 인원수 더하기
for (int r = 1; r < x + d1; r++) {
    for (int c = 1; c <= y; c++) {
        if (fifth[r][c]) break; //경계선 만나면 다음줄로
        popu[0] += map[r][c];
    }
}

//2번 선거구
for (int r = 1; r <= x + d2; r++) {
    for (int c = N; c >= y + 1; c--) {//열을 뒤에서부터 읽음
        if (fifth[r][c]) break;
        popu[1] += map[r][c];
    }
}

//3번 선거구
for (int r = x + d1; r <= N; r++) {
    for (int c = 1; c < y - d1 + d2; c++) {
        if (fifth[r][c]) break;
        popu[2] += map[r][c];
    }
}

//4번 선거구
for (int r = x + d2 + 1; r <= N; r++) {
    for (int c = N; c >= y - d1 + d2; c--) {//열을 뒤에서부터 읽음
        if (fifth[r][c]) break;
        popu[3] += map[r][c];
    }
}

5. 5번 선거구 = 전체 인구수 - popu배열 전체 합

//5번 선거구 인원수 구하기
int tempSum = 0;
for (int k = 0; k < 4; k++) {
    tempSum += popu[k];
}
popu[4] = totalPopu - tempSum;

6. popu 배열을 정렬해서 최대값과 최소값의 차이를 구해 전체 인구 차이의 최소값을 갱신한다

Arrays.sort(popu);

minPopu = Math.min(minPopu, (popu[4] - popu[0])); //최대-최소 인구수 가장 작은 값 갱신

전체 코드

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

public class Main_17779_게리맨더링2 {
    static int N, totalPopu;
    static int[] popu; //인구수를 저장할 배열
    static int[][] map;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        totalPopu = 0;
        map = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                totalPopu += map[i][j]; //총 인구수를 구함
            }
        }//end input

        //(x, y) (dx, dy)를 정한다
        //정한 조건에 따라 경계선을 표시한다
        //1~4번 선거구를 구하고 popu 배열에 순서대로 넣는다
        //5번 선거구이면 총인구수 - popu합을 빼서 5번 선거구 인구수로 넣어준다
        //배열 정렬하고 (맨 뒤 - 맨 앞)을 구해서 최소값 갱신

        int minPopu = Integer.MAX_VALUE;

        for (int x = 1; x <= N; x++) {
            for (int y = 1; y <= N; y++) {
                for (int d1 = 1; d1 <= N; d1++) {
                    for (int d2 = 1; d2 <= N; d2++) {

                        //1. 의 d1, d2에 대한 길이 조건에 해당되지 않으면 탐색 안 함
                        if (x + d1 + d2 > N) continue;
                        if (y - d1 < 1 || y + d2 > N) continue;

                        popu = new int[5];

                        //5번 선거구의 경계선을 지역구 배열에 true 표시
                        //각 지역구별로 다르게 범위를 구하면서 인구수 저장
                        boolean[][] fifth = new boolean[N + 1][N + 1];
                        //경계선 긋기
                        for (int r = x, c = y; r <= x + d1; r++, c--)
                            fifth[r][c] = true;
                        for (int r = x, c = y; r <= x + d2; r++, c++)
                            fifth[r][c] = true;
                        for (int r = x + d1, c = y - d1; r <= x + d1 + d2; r++, c++)
                            fifth[r][c] = true;
                        for (int r = x + d2, c = y + d2; r <= x + d2 + d1; r++, c--)
                            fifth[r][c] = true;

                        //한줄씩 범위대로 탐색
                        //1번 선거구 인원수 더하기
                        for (int r = 1; r < x + d1; r++) {
                            for (int c = 1; c <= y; c++) {
                                if (fifth[r][c]) break; //경계선 만나면 다음줄로
                                popu[0] += map[r][c];
                            }
                        }

                        //2번 선거구
                        for (int r = 1; r <= x + d2; r++) {
                            for (int c = N; c >= y + 1; c--) {//열을 뒤에서부터 읽음
                                if (fifth[r][c]) break;
                                popu[1] += map[r][c];
                            }
                        }

                        //3번 선거구
                        for (int r = x + d1; r <= N; r++) {
                            for (int c = 1; c < y - d1 + d2; c++) {
                                if (fifth[r][c]) break;
                                popu[2] += map[r][c];
                            }
                        }

                        //4번 선거구
                        for (int r = x + d2 + 1; r <= N; r++) {
                            for (int c = N; c >= y - d1 + d2; c--) {//열을 뒤에서부터 읽음
                                if (fifth[r][c]) break;
                                popu[3] += map[r][c];
                            }
                        }

                        //인구수가 0인 곳이 있으면 계산 안하고 넘어감
                        if (popu[0] == 0 || popu[1] == 0 || popu[2] == 0 || popu[3] == 0) {
                            break;
                        }

                        //5번 선거구 인원수 구하기
                        int tempSum = 0;
                        for (int k = 0; k < 4; k++) {
                            tempSum += popu[k];
                        }
                        popu[4] = totalPopu - tempSum;

                        Arrays.sort(popu);

                        minPopu = Math.min(minPopu, (popu[4] - popu[0])); //최대-최소 인구수 가장 작은 값 갱신

                    }
                }
            }
        }//end 4 for

        System.out.println(minPopu);

    }//end main
}

풀고 나니 어려운 문제가 아니었으나, 문제를 이해하는데 시간이 오래 걸렸다.

조건에 나온대로 for문의 범위를 정하면 금방 풀 수 있는 문제였다. 난 금방 못 풀었지만.