맨 위의 전구는 한 번씩 다 껐다 켜본다.

모든 전구는 2번 이상 건드리지 않는다.


대충 나오는 시간복잡도

O(2^N*N^2)

=> O(2^N)

N은 최대 18





풀이 방법 : 위의 전구가 켜져있으면 끈다.

근데 맨 위의 전구는 방법이 없다.

그래서 다 해본다.

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/14927
* BOJ 백준온라인져지 14927 전구 끄기 풀이
*/
using namespace std;
int yyyy[] = {0, 0, 1, 0, -1};
int xxxx[] = {0, -1, 0, 1, 0};
int result = 1e9, N;
int min (int a, int b) {
return a < b ? a : b;
}
void recursive2 (vector<vector<int> > lights, int count) {
for (int i = 2; i < N; i++) {
for (int j = 1; j < N; j++) {
if (lights[i - 1][j]) {
count++;
for (int k = 0; k < 5; k++) {
int x = i + xxxx[k], y = j + yyyy[k];
if (x <= 0 || y <= 0 || x >= N || y >= N) continue;
lights[x][y] = lights[x][y] * -1 + 1;
}
}
}
}
bool isBreaked = false;
for (int i = 1; i < N; i++) {
for (int j = 1; j < N; j++) {
if (lights[i][j]) {
isBreaked = true;
goto breakLoop;
}
}
}
breakLoop:
if (!isBreaked) result = min(count, result);
}
void recursive1 (vector<vector<int> > lights, int length) {
int count = 0;
for (int i = 0; i < N - 1; i++) {
if (length & 1 << i) {
count++;
for (int k = 0; k < 5; k++) {
int x = 1 + xxxx[k], y = i + 1 + yyyy[k];
if (x <= 0 || y <= 0 || x >= N || y >= N) continue;
lights[x][y] = lights[x][y] * -1 + 1;
}
}
}
recursive2(lights, count);
}
int main () {
scanf("%d", &N);
N++;
vector<vector<int> > originalLights;
originalLights.resize(N);
for (int i = 1; i < N; i++) {
originalLights[i].resize(N);
for (int j = 1; j < N; j++) {
scanf("%d", &originalLights[i][j]);
}
}
for (int i = (1 << (N - 1)) - 1; i >= 0; i--) {
recursive1(originalLights, i);
}
printf("%d", result == 1e9 ? -1 : result);
}
view raw BOJ_14927.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 11279 최대 힙 풀이  (1) 2017.12.30
BOJ 백준온라인져지 1927 최소 힙 풀이  (0) 2017.12.28
BOJ 백준온라인져지 2623 음악프로그램 풀이  (0) 2017.12.23
애니팡같은 게임  (0) 2017.12.21
BOJ 백준온라인져지 1766 문제집 풀이  (0) 2017.12.21

완전 그래프는 모든 vertex가 연결돼있다.


출력하는건 사전순이다.


그래서 현재 vertex에서 사전순으로 제일 가까운것을 출력하면 된다.


그런데 N(N-1) 번째에는 1이 출력되고

N(N-2)번째에는 N이 출력된다.


이 방법을 이용하면 쉽게 풀이가능

#include <cstdio>
/**
* https://www.acmicpc.net/problem/14926
* BOJ 백준온라인져지 14926 Not Equal 풀이
*/
int main(){
int N;
scanf("%d", &N);
N++;
int **edges = new int*[N];
bool **visited = new bool*[N];
for(int i = 0; i < N; i++) edges[i] = new int[N], visited[i] = new bool[N];
int currentVertex = 0, preVertex = 0;
int forLoopCount = (N - 1) * (N - 2) / 2;
visited[1][N - 1] = visited[N - 1][1] = true;
while(forLoopCount--){
for(int i = 1; i < N; i++){
if(i == currentVertex || visited[currentVertex][i]) continue;
visited[currentVertex][i] = visited[i][currentVertex] = true;
currentVertex = i;
break;
}
printf("a%d ", currentVertex);
}
printf("a1");
}
view raw BOJ_14926.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1766 문제집 풀이  (0) 2017.12.21
BOJ 백준온라인져지 1005 ACM Craft 풀이  (0) 2017.12.19
BOJ 백준온라인져지 14925 목장 건설하기 풀이  (0) 2017.12.16
BOJ 백준온라인져지 14924 폰 노이만과 파리 풀이  (0) 2017.12.16
BOJ 백준온라인져지 2206 벽 부수고 이동하기 풀이  (0) 2017.12.15

dp로 풀었다. O(NM)


입력차례대로 위칸과 왼쪽칸과 왼쪽위 대각선 칸을 비교해서 가장 작은값 + 1로 새로운 정사각형을 만들 수 있다.

#include <cstdio>
/**
* https://www.acmicpc.net/problem/14925
* BOJ 백준온라인져지 14925 목장 건설하기 풀이
*/
int min(int a, int b){
return a < b ? a : b;
}
int max(int a, int b){
return a > b ? a : b;
}
int main(){
int rowSize, columnSize, result = 0;
scanf("%d%d", &rowSize, &columnSize);
rowSize++, columnSize++;
bool **map = new bool*[rowSize];
int **dp = new int*[rowSize];
for(int i = 0; i < rowSize; i++){
map[i] = new bool[columnSize];
map[i][0] = true;
dp[i] = new int[columnSize];
}
for(int i = 0; i < columnSize; i++){
map[0][i] = true;
}
for(int i = 1; i < rowSize; i++){
for(int j = 1; j < columnSize; j++){
dp[i][j] = 0;
int temp;
scanf("%d", &temp);
map[i][j] = temp == 0;
if(map[i][j]){
dp[i][j] = 1;
int t = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
dp[i][j] = t + 1;
result = max(dp[i][j], result);
}
}
}
printf("%d", result);
}
view raw BOJ_14925.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1005 ACM Craft 풀이  (0) 2017.12.19
BOJ 백준온라인져지 14926 Not Equal 풀이  (0) 2017.12.17
BOJ 백준온라인져지 14924 폰 노이만과 파리 풀이  (0) 2017.12.16
BOJ 백준온라인져지 2206 벽 부수고 이동하기 풀이  (0) 2017.12.15
BOJ 백준온라인져지 14923 미로탈출 풀이  (0) 2017.12.15

NYPC에서 풀었던 문제와 유사하다.


NYPC문제때는 급수를 이용해서 풀었었는데 틀리다고 나왔었다.


#include <cstdio>
/**
* https://www.acmicpc.net/problem/14924
* BOJ 백준온라인져지 14924 폰 노이만과 파리 풀이
*/
int main(){
int trainVelocity, aFlyVelocity, distance;
scanf("%d%d%d", &trainVelocity, &aFlyVelocity, &distance);
printf("%d", distance / (trainVelocity * 2) * aFlyVelocity);
}
view raw BOJ_14924.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 14926 Not Equal 풀이  (0) 2017.12.17
BOJ 백준온라인져지 14925 목장 건설하기 풀이  (0) 2017.12.16
BOJ 백준온라인져지 2206 벽 부수고 이동하기 풀이  (0) 2017.12.15
BOJ 백준온라인져지 14923 미로탈출 풀이  (0) 2017.12.15
BOJ 백준온라인져지 1456 거의 소수 풀이  (0) 2017.12.14

벽을 한 번 부신다!!


코드가 길지 않으니 설명은 없다.

#include <cstdio>
#include <queue>
/**
* https://www.acmicpc.net/problem/14923
* BOJ 백준온라인져지 14923 미로탈출 풀이
*/
#define INF 99999999
using namespace std;
int xxxx[] = {0, 1, 0 , -1};
int yyyy[] = {-1, 0, 1 , 0};
class coordinate{
public:
int x, y;
bool z;
coordinate(int _x, int _y, bool _z) :x(_x), y(_y), z(_z){}
};
int min(int a, int b){
return a < b ? a : b;
}
int main(){
int rowSize, columnSize;
scanf("%d%d", &rowSize, &columnSize);
rowSize++, columnSize++;
int ***resultArray = new int**[rowSize], **map = new int*[rowSize];
int startX, startY;
int endX, endY;
scanf("%d%d%d%d", &startX, &startY, &endX, &endY);
for(int i = 1; i < rowSize; i++){
resultArray[i] = new int*[columnSize];
map[i] = new int[columnSize];
for(int j = 1; j < columnSize; j++){
resultArray[i][j] = new int[2];
scanf("%d", &map[i][j]);
resultArray[i][j][0] = resultArray[i][j][1] = INF;
}
}
resultArray[startX][startY][0] = 0;
queue<coordinate> queue;
queue.push(coordinate(startX, startY, false));
while(!queue.empty()){
coordinate polledData = queue.front();
queue.pop();
int x = polledData.x;
int y = polledData.y;
bool z = polledData.z;
int moveCount = resultArray[x][y][z] + 1;
for(int i = 0 ; i < 4; i++){
int newX = xxxx[i] + x;
int newY = yyyy[i] + y;
if(newX <= 0 || newX >= rowSize || newY <= 0 || newY >= columnSize) continue;
if(map[newX][newY] == 0 && moveCount < resultArray[newX][newY][z]){
queue.push(coordinate(newX, newY, z)), resultArray[newX][newY][z] = moveCount;
}else if(map[newX][newY] == 1 && !z && moveCount < resultArray[newX][newY][1]){
queue.push(coordinate(newX, newY, 1)), resultArray[newX][newY][1] = moveCount,
resultArray[newX][newY][2] = 1;
}
}
}
int result = min(resultArray[endX][endY][0], resultArray[endX][endY][1]);
if(result == INF) result = -1;
printf("%d", result);
}
view raw BOJ_14923.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 14924 폰 노이만과 파리 풀이  (0) 2017.12.16
BOJ 백준온라인져지 2206 벽 부수고 이동하기 풀이  (0) 2017.12.15
BOJ 백준온라인져지 1456 거의 소수 풀이  (0) 2017.12.14
BOJ 백준온라인져지 14921 용액 합성하기 풀이  (0) 2017.12.14
BOJ 백준온라인져지 2530 인공지능 시계 풀이  (0) 2017.12.14

용액의 특성값이 중복이 된다는 생각을 안하고 풀어서 1일이 걸렸다.


코드의 변화가 많이 있었는데

처음에는 순차적으로 검색하는걸 작성하다가 시간초과가 날 예상을 하고 안짰다.

다음에는 순차적으로 하는데 idx를 저장해서 그 idx만큼만 돌게했다. 시간초과

다음에는 l과 r을 두고 만나는 방식으로 했는데 틀렸다. 양수와 음수를 가지고 계산함.

다음에는 양수와 음수를 생각하지 않고 l과 r을 두고 만나는 방식을 사용함. (정답)

#include <cstdio>
/**
* https://www.acmicpc.net/problem/14921
* BOJ 백준온라인져지 14921 용액 합성하기 풀이
*/
using namespace std;
int abs(int a){
return a > 0 ? a : -a;
}
int min(int a, int b){
int aa = abs(a);
int bb = abs(b);
return aa < bb ? a : b;
}
int main(){
int N;
scanf("%d", &N);
int *list = new int[N];
for(int i = 0; i < N; i++){
scanf("%d", &list[i]);
}
int maximum = 1000000000, l = 0, r = N - 1;
do{
if(abs(maximum) > abs(list[l] + list[r])){
maximum = list[l] + list[r];
}
if(abs(list[l] + list[r]) >= abs(list[l] + list[r - 1])){
r--;
}else if(r + 1 < N && abs(list[l] + list[r]) > abs(list[l] + list[r + 1])){
r++;
}else{
l++;
}
}while(l < r);
printf("%d", maximum);
}
view raw BOJ_14921.cpp hosted with ❤ by GitHub


#include <cstdio>
/**
* https://www.acmicpc.net/problem/14921
* BOJ 백준온라인져지 14921 용액 합성하기 풀이
*/
using namespace std;
int abs(int a){
return a > 0 ? a : -a;
}
int min(int a, int b){
int aa = abs(a);
int bb = abs(b);
return aa < bb ? a : b;
}
int main(){
int N;
scanf("%d", &N);
int *list = new int[N];
for(int i = 0; i < N; i++){
scanf("%d", &list[i]);
}
int maximum = 1000000000, l = 0, r = N - 1;
do{
if(abs(maximum) > abs(list[l] + list[r])){
maximum = list[l] + list[r];
}
if(abs(list[l] + list[r]) >= abs(list[l] + list[r - 1])){
r--;
}else if(r + 1 < N && abs(list[l] + list[r]) > abs(list[l] + list[r + 1])){
r++;
}else{
l++;
}
}while(l < r);
printf("%d", maximum);
}
view raw BOJ_14921.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 14923 미로탈출 풀이  (0) 2017.12.15
BOJ 백준온라인져지 1456 거의 소수 풀이  (0) 2017.12.14
BOJ 백준온라인져지 2530 인공지능 시계 풀이  (0) 2017.12.14
BOJ 백준온라인져지 2525 오븐 시계 풀이  (0) 2017.12.14
BOJ 백준온라인져지 9987 포켓몬 마스터 풀이  (0) 2017.12.14

소수 계산은 아직 익숙하지가 않다.


그래서 다른 답들을 참고해봤는데, 문자열로 받아서 정수형으로 변환하고 처리하는게 많은거 같다.

또는 아주작은 숫자를 더해서 반올림 해주는거 같다.

#include <cstdio>
#include <vector>
#include <math.h>
/**
* https://www.acmicpc.net/problem/14919
* BOJ 백준온라인져지 14919 분포표 만들기 풀이
*/
#define MUL 1e+6
using namespace std;
int main(){
int m;
scanf("%d", &m);
double temp;
vector<int> a;
int bMin = 0;
int b = MUL / m, bMax;
while(scanf("%lf", &temp) != EOF){
a.push_back(ceil((double)temp * MUL));
}
for(int j = 0, count = 0, size = a.size(); j < m; j++, count = 0){
bMax = (j + 1) * b;
for(int i = 0; i < size; i++)
if(bMin <= a[i] && a[i] < bMax) count++;
printf("%d ", count);
bMin = bMax;
}
}
view raw BOJ_14919.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2525 오븐 시계 풀이  (0) 2017.12.14
BOJ 백준온라인져지 9987 포켓몬 마스터 풀이  (0) 2017.12.14
BOJ 백준온라인져지 14918 더하기 풀이  (0) 2017.12.13
BOJ 백준온라인져지 14920 3n+1 수열 풀이  (0) 2017.12.13
BOJ 백준온라인져지 1916 최소비용 구하기 풀이  (0) 2017.12.12
#include <cstdio>
/**
* https://www.acmicpc.net/problem/14918
* BOJ 백준온라인져지 14918 더하기 풀이
*/
int main(){
int A, B;
scanf("%d%d", &A, &B);
printf("%d", A + B);
}
view raw BOJ_14918.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 9987 포켓몬 마스터 풀이  (0) 2017.12.14
BOJ 백준온라인져지 14919 분포표 만들기 풀이  (0) 2017.12.13
BOJ 백준온라인져지 14920 3n+1 수열 풀이  (0) 2017.12.13
BOJ 백준온라인져지 1916 최소비용 구하기 풀이  (0) 2017.12.12
BOJ 백준온라인져지 2953 나는 요리사다 풀이  (0) 2017.12.11 
     C(n+1) = C(n)/2     (C(n)이 짝수일 때)
            = 3*C(n)+1   (C(n)이 홀수일 때)
#include <cstdio>
/**
* https://www.acmicpc.net/problem/14920
* BOJ 백준온라인져지 14920 3n+1 수열 풀이
*/
int main(){
int N, count = 1;
scanf("%d", &N);
while(N != 1){
if(N % 2) N = 3 * N + 1;
else N /= 2;
count++;
}
printf("%d", count);
}
view raw BOJ_14920.cpp hosted with ❤ by GitHub

점화식이 이미 세워져있는걸 코드로 구현하면 된다.

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 14919 분포표 만들기 풀이  (0) 2017.12.13
BOJ 백준온라인져지 14918 더하기 풀이  (0) 2017.12.13
BOJ 백준온라인져지 1916 최소비용 구하기 풀이  (0) 2017.12.12
BOJ 백준온라인져지 2953 나는 요리사다 풀이  (0) 2017.12.11
BOJ 백준온라인져지 1916 최소비용 구하기 풀이  (0) 2017.12.11

pow를 이용해 자리를 변경해줬다.

#include <cstdio>
#include <math.h>
/**
* https://www.acmicpc.net/problem/13410
* BOJ 백준온라인져지 13410 거꾸로 구구단 풀이
*/
int MAX(int a, int b){
return a > b ? a : b;
}
int main(){
int N, K, max = 0;
scanf("%d%d", &N, &K);
for(int i = 1; i <= K; i++){
int temp = 0;
int multiply = N * i;
temp = multiply;
int cnt = 0;
while(temp >= 10){
temp /= 10;
cnt++;
}
temp = 0;
for(int j = cnt; j >= 0; j--){
int f = pow(10, j);
int ff = multiply / f;
temp += ff * pow(10, cnt - j);
multiply %= f;
}
max = MAX(temp, max);
}
printf("%d", max);
}
view raw BOJ_13410.cpp hosted with ❤ by GitHub


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1916 최소비용 구하기 풀이  (0) 2017.12.11
BOJ 백준온라인져지 2702 초6 수학 풀이  (0) 2017.12.11
BOJ 백준온라인져지 2711 오타맨 고창영 풀이  (0) 2017.12.11
BOJ 백준온라인져지 6359 만취한 상범 풀이  (0) 2017.12.11
BOJ 백준온라인져지 6378 디지털 루트 풀이  (0) 2017.12.11

+ Recent posts

티스토리툴바