내맘대로블로그

요청사항에 따라 구현하였다. 구현 중에 주의해야할 부분은 구름은 경계를 넘나들어서 나머지 연산을 이용하여 올바르게 값을 넣어주어야하고. 바로 직전에 구름이 있던 자리엔 구름이 생기면 안 되기에 이 점도 유의해줘야한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107import java.io.*;import java.util.*; class Main { static int N;..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 중간 중간의 목적지를 분명하게 정하는 것이 중요한 문제! 1. 아기 상어의 위치에서 최단 거리 내 갈 수 있는 모든 물고기 위치의 경우의 수를 구한다. 2. 물고기가 두 마리 이상이라면 기준에 맞게 정렬한다. 3. 중간 중간 상어를 관리해주기 위해 자료형 shark를 만들었다. import java.io.*; import java.util.*; class Main { static int N..

16234번: 인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 좀더 간결하게 풀이해서 포스팅 (링크) 이전엔 방문체크를 다른 배열을 둬서 했는데 그런 것 없이 한번에 풀이하여서 좀더 깔끔한 풀이가 됨 풀이 개요 BFS나 DFS 와 같이 완전 탐색 이용해서 풀이하면 되는 문제. 나는 BFS를 사용하였고, BFS 두 번 돌리면 시간 초과가 일어나기에 한번 BFS를 돌릴 때, 인구 이동시 필요한 값들을 다 저장해야한다. 문제 풀이시 약간 헷갈려서 같은 역할을 하는 방문 체크를 위한 배열이 2..

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..