내맘대로블로그

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 백준의 삼성 문제들은 배열을 잘 다루면 비교적 쉽게 풀리는 문제다. 이것도 골드2지만 배열을 잘 다룬다면 ㅠㅠ 쉽게 풀수 있지 않을까 생각한다. 1. 상하좌우를 5가지의 중복순열로 만든다. 2. 경우의 수에 맞게 보드를 조합한다. 주의 : 처음 지도의 값은 변하면 안 되므로 복사해서 사용해야하는데 배열의 주소 값이 아닌 실제 값을 복사하도록 하자! import java..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 1. Queue : 뱀의 움직임 관리 Queue moveInfo 2. Deque : 뱀 자체 관리 Deque snake 3. int[][] : 사과의 위치 관리 map 4. class Dot : 뱀이나 사과의 위치 값 관리 5. class Snake : 뱀이 움직일 위치 정보 기록 6. move() : 뱀이 움직임에 대한 메서드 뱀이 사과를 먹으면 커지고 안 먹으면 안 커지거나 코너에서의 방향 전환에 대..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 삼성 문제 특성상 시키는 대로만 하면 되는데... 나의 고질적인 row/col의 헷갈림과 쓸데없는 반복문 돌림으로 고생했던 문제 문제는 백트래킹을 이용해서 풀면 된다. 삼성 문제의 경우 최대 횟수가 정해져있어서 이것을 잘 고려한다면 생각보다 백트래킹으로 인해 시간초과가 뜨진 않을까의 걱정을 덜 수도 있다. 풀이 포인트를 정리하자면, 1. 사다리 게임을 통해 결과 확인 (처음부터 원하던 결과여서 ..

www.acmicpc.net/problem/14720 14720번: 우유 축제 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 그리디로도 풀 수 있다는데 DP로 풀었다. 일정한 순서가 있고(딸기 우유를 마셔야 초코 우유를 마실 수 있고, 초코 우유를 마셔야 바나나 우유를 마실 수 있고, 바나나 우유를 마신 다음에는 딸기 우유를 마셔야하는 것!) 이러한 순서가 있다보니, 내가 마신 종류별 우유의 갯수는 바로 전 순서와 같거나(내가 마실 우유의 위치가 아닌 경우) 전 순서보다 하나 더 많다.(마실 수 있는 우유의 위치인 경우) -> 0 1 2..

Gold 5, 이 문제는 런타임에러가 굉장히 발목을 잡았는데, 모듈러연산을 이용하여 마법사 상어의 이동을 처리했다고 생각했는데 오산이었다. 스피드가 엄청나게 클 경우 모듈러 연산을 사용하여도 런타임 에러가 발생할 수 있다. 파이어볼 문제에서는 맵을 중심으로 풀건지 파이어볼을 중심으로 풀 건지를 선택해야한다. 나의 경우엔 파이어볼 객체에 파이어볼의 위치도 넣어주면서 리스트로 관리하는 방식으로 코딩하였다. 예외 처리에 특히 주의한다면 큰 무리는 없는 문제라고 생각한다. import java.io.*; import java.util.*; class Main { static int N, M, K, answer; static List[][] map; static int[][] dirs = {{-1, 0},{-1,..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제만 보고는 저거를 다 돌려야하나 귀찮고 막막하다 생각을 했다. 다른 블로그들을 참고하니 ㅜ 모양을 제외하고는 길이가 4인 최단 경로라는 점에서 착안하여 풀이하면 된다고 하였다. 모든 경우를 구해야하기에 백트래킹을 이용하였고, ㅜ 모양의 경우엔, 한 모양에서 길이가 3인 경우가 최단 경로이기에 따로 분리하여 풀이하였다. 최대 값을 구하기 위해서 백트래킹시에 사용되는 메서드에 현재 위치의 값을 합할 매개변수로 ..

www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 일반적인 시뮬레이션에 정렬기능이 추가된 문제다. 순서대로 풀이하다가 봄 부분에서 정렬을 해주는 것이 포인트인 문제. 정렬부분에서 상당히 애먹었는데, 우선순위 큐로 풀었더니 시간초과가 났는지 바로 틀렸습니다. 가 떴다. 그래서 Tree라는 구조체를 만들어서 age기준으로 정렬하여 수행하였다. 시간을 주의 깊게 봐야겠다. import java.io.*; import java.util.*; class..

www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net Gold 4 횟수 갯수 만큼의 단계가 주어지면 그 단계(= 칸수)를 기준으로 회전하고 얼음을 녹인다. 1. 2^n만큼 구역을 나눠주고 그 칸을 회전한다. 2. 전체 탐색하며 얼음을 녹여준다. 3. 1,2를 주어진 단계만큼 수행한다. 4. 제일 큰 덩어리와 얼음의 합을 출력한다. -> 나의 경우엔 회전과 얼음을 녹이는 부분에서 시간이 많이 걸렸다. [회전 부분] public static int..

www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net Gold 5 완전 탐색! DFS도 되고 BFS도 되지만 난 BFS로 풀이! 1. 완전 탐색(for 문 2번 돌리기)로 동서남북을 확인하며 범위내에 해당하는지 확인 1) 해당하면 queue에 넣어서 인구 이동이 가능한지를 탐색(BFS나 DFS사용) 가능하다면 flag를 둬서 가능함을 표시(나중에 인구 이동 발생 횟수를 증가 시키기 위함) 2) 이동 가능한 인구 수 의 합계를 구하기 위해 변수를 정하..

www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net Gold 5 나의 경우엔 안 되는 상점의 조합을 구해서 풀었다. 안 되는 상점의 조합은 DFS, 백트래킹이용 상점을 이용한 최단 거리는 BFS를 풀려고 했지만 시간 초과가 나왔다. 그래서 DFS + 완전 탐색로 풀었더니 정답! 거리 구하는 부분에서 헤매지만 않았으면 더 잘 풀었을 문제 ㅠㅠ package com.example.demo; import java.io.*; import java...